现实世界中的图往往在结点和边上包含描述信息，可达性查询是图数据管理和挖掘中的基本操作之一。针对图数据中标签约束的可达性计算问题，提出一种基于递归划分的可达性计算方法RP-Hop。该算法基于层次划分思想，利用独立集性质，在保持标签和可达性前提下对大规模图进行递归划分，并结合贪婪扩展思想和递归编码，为标签约束的可达性查询提供压缩索引。经过合成和真实数据集上的实验，结果表明，RP-Hop算法不仅降低了索引大小和构建时间，而且提高了查询效率。%Many of the real-world graphs are edge-labeled or node-labeled.A foundational operation on these labeled graphs is how to answer reachability queries fast.For the label-constraint reachability computation problem,a computation method called RP-Hop based on recursive partition was proposed.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 data sets demonstrate that RP-Hop can reduce index size and construction time,and guarantee the query efficiency.
展开▼
