| 基于压缩全文索引的演变图查询 |
| |
| 引用本文： | 肖洋,朱青,吴粤皖.基于压缩全文索引的演变图查询[J].计算机工程与应用,2015(2):117-124. |
| |
| 作者姓名： | 肖洋 朱青 吴粤皖 |
| |
| 作者单位： | 1. 中国人民大学 信息学院 计算机系，北京 100872; 中国人民大学 信息学院 数据工程与知识工程教育部重点实验室，北京 100872
2. 中国人民大学 信息学院 计算机系,北京,100872 |
| |
| 基金项目： | 国家自然科学基金(No.61070053)。 |
| |
| 摘 要： | 演变图中含有大量的时间和空间信息,其中某些空间信息随着时间的推移表现出相似的演变规律。给出了一种演变图查询模型,可以挖掘出在相同时间范围内具有相同变化规律的演变子图。但是演变图的规模往往是巨大的,当需要对其进行多次查询时,每次遍历整个演变图将带来非常高的查询代价,而现有的基于枚举的哈希索引算法又使得预处理过程拥有相当大的时间和空间开销,为了减少对大规模演变图的预处理代价,将压缩的全文索引技术应用于演变图,它基于涡轮转换和后缀数组。在构建后缀数组时,给出了两种不同的线性算法,确保了预处理过程的稳定性。通过在Facebook、Enron邮件系统以及模拟数据集上的实验,评估了该算法的可行性、效率以及可扩展性。
|
| 关 键 词： | 演变图 查询 演变子图 后缀数组 压缩全文索引 |
Querying on evolving graphs based on compressed full-text index |
| |
| XIAO Yang,ZHU Qing,WU Yuewan.Querying on evolving graphs based on compressed full-text index[J].Computer Engineering and Applications,2015(2):117-124. |
| |
| Authors: | XIAO Yang ZHU Qing WU Yuewan |
| |
| Affiliation: | XIAO Yang;ZHU Qing;WU Yuewan;Department of Computer Science, School of Information, Renmin University of China;Key Laboratory of Data Engineering and Knowledge Engineering, School of Information, Renmin University of China; |
| |
| Abstract: | |
| |
| Keywords: | evolving graph query evolving subgraph suffix array compressed full-text index |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
