时序图上动态子图查询优化算法  

Querying Optimization Algorithm for Dynamic Subgraph on Time-Evolving Graph

作　　者：朱青[1,2] 李红[1,2] 

机构地区：[1]中国人民大学教育部数据工程与知识工程重点实验室,北京100872 [2]中国人民大学信息学院计算机系,北京100872

出　　处：《计算机科学与探索》2014年第11期1324-1333,共10页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金;上海市高可信计算重点实验室开放课题~~

摘　　要：挖掘时序图中的特定模式,能够有效地发现有价值的信息,并进行预测与决策支持,因此动态子图的查询及索引优化成为时序图研究的一个热点。研究了聚焦在动态子图的快速查询,着重探讨了索引优化,给出了查询模型的定义及基本查询算法。针对查询算法进行索引优化,提出了两种不同的建立索引的方法,波形索引及二叉树索引。为了验证索引的适用条件,设计了相应的实验,并使用随机数据集对实验程序进行测试,从时间消耗和空间占用的角度对两种索引的运行效率进行了验证分析。波形索引的优势在于存储结构简单,适用于边长度较长边数量不多的情况。二叉树索引的查询速度快,适用于边长度较短边数目较多的情况。Finding specific patterns in the time-evolving graph can help people effectively get hidden information in the data, so the dynamic subgraph query and index optimization have become a hotspot in the research of the evolving graph. This paper selects dynamic subgraph query as a research point, and discusses index optimization emphatically. This paper firstly gives the definition of the query model and the basic query algorithm. Then, this paper provides two different indexing methods, waveform index and binary tree index. To test the applicability of the index, this paper designs the corresponding experiments and uses randomly generated datasets to test experiments, while analyzing the efficiency from time consumption and space utilization. The experiments show that waveform index has the advantage of simple storage structure, which is suitable for the situation of long edge length but small edge number. Binary tree index has good performance in query speed, which is suitable for the situation of short edge length and large edge number.

关 键 词：查询优化算法 时序图 动态子图 索引优化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]