Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths
Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths
复制标题
DOI：
10.1145/2505515.2505724
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Yosuke Yano;Takuya Akiba;Yoichi Iwata;Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Yosuke Yano;Takuya Akiba;Yoichi Iwata;Yuichi Yoshida
在有向图上进行可达性查询作为一种最基本、最重要的操作，在许多涉及图形数据的应用中是普遍存在的。然而，在大规模图上有效地处理它们仍然具有很大的挑战性。基于传递闭包的方法消耗的索引空间太大，而基于在线搜索的方法回答查询的速度太慢。基于标记的方法可以同时获得较小的索引大小和查询时间，但以前的索引算法对于处理当天的大型图来说根本不具有可扩展性。在本文中，我们提出了新的标签为基础的方法，可达性查询，被称为修剪地标标签和修剪路径标签。它们遵循2-hop cover和3-hop cover的框架，但它们的索引算法基于最近的修剪标记概念，并将索引时间提高了几个数量级，从而适用于具有数千万个顶点和边的大型图。我们的实验结果表明，他们达到了显着的折衷之间的快速查询时间，小索引大小和可扩展性，以前的方法从来没有能够实现。此外，我们还讨论了我们的方法的效率的成分，通过一个新的理论分析的基础上图子理论。
Answering reachability queries on directed graphs is ubiquitous in many applications involved with graph-shaped data as one of the most fundamental and important operations. However, it is still highly challenging to efficiently process them on large-scale graphs. Transitive-closure-based methods consume prohibitively large index space, and online-search-based methods answer queries too slowly. Labeling-based methods attain both small index size and query time, but previous indexing algorithms are not scalable at all for processing large graphs of the day. In this paper, we propose new labeling-based methods for reachability queries, referred to as pruned landmark labeling and pruned path labeling. They follow the frameworks of 2-hop cover and 3-hop cover, but their indexing algorithms are based on the recent notion of pruned labeling and improve the indexing time by several orders of magnitude, resulting in applicability to large graphs with tens of millions of vertices and edges. Our experimental results show that they attain remarkable trade-offs between fast query time, small index size and scalability, which previous methods have never been able to achieve. Furthermore, we also discuss the ingredients of the efficiency of our methods by a novel theoretical analysis based on the graph minor theory.