| X-Hop:传递闭包的多跳数压缩存储和快速可达性查询 |
| |
| 引用本文： | 舒虎,崇志宏,倪巍伟,卢山,徐立臻. X-Hop:传递闭包的多跳数压缩存储和快速可达性查询[J]. 计算机科学, 2012, 39(3): 149-152 |
| |
| 作者姓名： | 舒虎 崇志宏 倪巍伟 卢山 徐立臻 |
| |
| 作者单位： | (东南大学计算机科学与工程学院 南京211189) |
| |
| 基金项目： | 国家自然科学基金(60973023,61003057)资助 |
| |
| 摘 要： | 海量图数据上的可达性查询是图数据管理的基本问题。目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储,再辅以快速查询算法来回答两顶点是否可达。在此基础上,重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法,提出了多跳(简称为X-Hop)压缩存储方法。通过采用生成树的结构对2-Hop中的中心顶点进行组织,X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量,从而极大地提高了压缩比。实验证明,X-Hop在索引的规模上要远远小于2-Hop存储,并且在查询效率上也取得优势。
|
| 关 键 词： | X-Hop 可达性查询 2-Hop标记 传递闭包压缩 |
X-Hop; Storage of Transitive Closure and Efficient Query Process |
| |
| SHU Hu,CHONG Zhi-hong,NI Wei-wei,LU Shan,XU Li-zhen. X-Hop; Storage of Transitive Closure and Efficient Query Process[J]. Computer Science, 2012, 39(3): 149-152 |
| |
| Authors: | SHU Hu CHONG Zhi-hong NI Wei-wei LU Shan XU Li-zhen |
| |
| Affiliation: | (School of (}c>mputer Science and Engineering, Southeast University,Nanjing 211189,China) |
| |
| Abstract: | Reachability query is one of the fundamental problems of management of massive directed graphs. This paper considered reachabihty query under the context of dense graphs. We proposed a storage schema, called X-Hop, which compresses the storage of 2-Hop via a multipl}hop schema. By organizing center vertexes in a tree structure, X-Hop storage delivers efficient query process in addition to high compression ratio. Extensive experiments demonstrate the efficiency of our proposal. |
| |
| Keywords: | X-Hop Reachability query 2-Hop labeling Transitive closure compression |
| 本文献已被 CNKI 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
