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

摘要：

挖掘时序图中的特定模式，能够有效地发现有价值的信息，并进行预测与决策支持，因此动态子图的查询及索引优化成为时序图研究的一个热点。研究了聚焦在动态子图的快速查询，着重探讨了索引优化，给出了查询模型的定义及基本查询算法。针对查询算法进行索引优化，提出了两种不同的建立索引的方法，波形索引及二叉树索引。为了验证索引的适用条件，设计了相应的实验，并使用随机数据集对实验程序进行测试，从时间消耗和空间占用的角度对两种索引的运行效率进行了验证分析。波形索引的优势在于存储结构简单，适用于边长度较长边数量不多的情况。二叉树索引的查询速度快，适用于边长度较短边数目较多的情况。

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

分类号：TP391(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.61070053;the Open Project of Shanghai Key Laboratory of Trustworthy Computing of China under Grant No.07dz22304

在线出版日期：2014-11-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1324-1333