X-Hop:传递闭包的多跳数压缩存储和快速可达性查询

计算机科学 ›› 2012, Vol. 39 ›› Issue (3): 149-152.

X-Hop:传递闭包的多跳数压缩存储和快速可达性查询

舒虎,崇志宏,倪巍伟,卢山,徐立臻

(东南大学计算机科学与工程学院南京211189)

出版日期:2018-11-16 发布日期:2018-11-16

X-Hop; Storage of Transitive Closure and Efficient Query Process

SHU Hu,CHONG Zhi-hong ,NI Wei-wei ,LU Shan ,XU Li-zhen

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 海量图数据上的可达性查询是图数据管理的基本问题。目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储，再辅以快速查询算法来回答两顶点是否可达。在此基础上，重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法，提出了多跳(简称为X-Hop)压缩存储方法。通过采用生成树的结构对2-Hop中的中心顶点进行组织，X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量，从而极大地提高了压缩比。实验证明，X-Hop在索引的规模上要远远小于2-Hop存储，并且在查询效率上也取得优势。

关键词: X-Hop，可达性查询，2-Hop标记，传递闭包压缩

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.

Key words: X-Hop,Reachability query,2-Hop labeling,Transitive closure compression

舒虎,崇志宏,倪巍伟,卢山,徐立臻. X-Hop:传递闭包的多跳数压缩存储和快速可达性查询[J]. 计算机科学, 2012, 39(3): 149-152. https://doi.org/

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. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed