递归划分的标签约束可达性计算方法* (2014年)

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