基于压缩全文索引的演变图查询

• 作者: 吴粤皖 朱青 肖洋
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 演变图 查询 演变子图 后缀数组 压缩全文索引
• 年，卷（期）: 2015,（2）
• 所属期刊栏目: 数据库、数据挖掘、机器学习
• 页码范围: 117-124
• 页数: 8页
• 分类号: TP391
• 字数: 8256字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1308-0190

摘要

演变图中含有大量的时间和空间信息，其中某些空间信息随着时间的推移表现出相似的演变规律。给出了一种演变图查询模型，可以挖掘出在相同时间范围内具有相同变化规律的演变子图。但是演变图的规模往往是巨大的，当需要对其进行多次查询时，每次遍历整个演变图将带来非常高的查询代价，而现有的基于枚举的哈希索引算法又使得预处理过程拥有相当大的时间和空间开销，为了减少对大规模演变图的预处理代价，将压缩的全文索引技术应用于演变图，它基于涡轮转换和后缀数组。在构建后缀数组时，给出了两种不同的线性算法，确保了预处理过程的稳定性。通过在Facebook、Enron邮件系统以及模拟数据集上的实验，评估了该算法的可行性、效率以及可扩展性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱青	中国人民大学信息学院计算机系	70	739	14.0	27.0
5	肖洋	中国人民大学信息学院计算机系	2	5	1.0	2.0
9	吴粤皖	中国人民大学信息学院计算机系	1	1	1.0	1.0