递归划分的标签约束可达性计算方法

现实世界中的图往往在结点和边上包含描述信息,可达性查询是图数据管理和挖掘中的基本操作之一。针对图数据中标签约束的可达性计算问题,提出一种基于递归划分的可达性计算方法 RP-Hop。该算法基于层次划分思想,利用独立集性质,在保持标签和可达性前提下对大规模图进行递归划分,并结合贪婪扩展思想和递归编码,为标签约束的可达性查询提供压缩索引。经过合成和真实数据集上的实验,结果表明,RP-Hop算法不仅降低了索引大小和构建时间,而且提高了查询效率。

A label constraint reachability computation method based on recursive partition

Many of the real-world graphs are edge-labeled or node labeled. A foundational operations on these labeled graphs is how to answer the reachability querying fast. For the label-constraint reachability computation problem, this paper proposed a computation method called RP-Hop based on Recursive Partition. RP-Hop first utilized the hierarchical structure and independent set property to partition the origin large graph recursively, while keeping reachability and labels on paths between node pairs simultaneously. Combined with greedy and recursive labeling strategies, RP-Hop produced a compressed index for label-constraint reachability queries. Experiments on synthetic and real-world graph datasets demonstrate that RP-Hop can reduce index size and construction time, and at the same time guarantee the query efficiency.