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

摘要

Reachability query is one of the fundamental problems of management of massive directed graphs. This paper considered reachability query under the context of dense graphs. We proposed a storage schema, called X-Hop, which compresses the storage of 2-Hop via a multiple-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.%海量图数据上的可达性查询是图数据管理的基本问题.目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储,再辅以快速查询算法来回答两顶点是否可达.在此基础上,重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法,提出了多跳(简称为X-Hop)压缩存储方法.通过采用生成树的结构对2-Hop中的中心顶点进行组织,X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量,从而极大地提高了压缩比.实验证明,X-Hop在索引的规模上要远远小于2-Hop存储,并且在查询效率上也取得优势.