Reachability and distance queries via 2-hop labels
Reachability and distance queries via 2-hop labels
复制标题
DOI：
10.1137/s0097539702403098
复制
发表时间：
2003-01-01
影响因子：
1.6
通讯作者：
Zwick, U
中科院分区：
文献类型：
--
作者：
Cohen, E;Halperin, E;Zwick, U
图表中的可及性和距离查询是众多应用程序的基础，从地理导航系统到互联网路由。其中一些应用程序涉及大图，但需要快速查询答案。我们提出了一个新的数据结构，用于表示图中的所有距离。数据结构的分布方式是可以将其视为将标签分配给顶点，因此仅使用U和V的标签可以回答涉及顶点U和V的查询。您的标签是基于2-Hop Covers图中最短路径或所有路径。对于最短路径，这样的覆盖物是一个最短路径的集合，因此，对于每两个顶点u和v，从u到v的最短路径是S的最短路径，是S的两个路径的串联。我们描述了一个有效的算法的算法。找到给定路径集合的几乎最佳的2跳盖。我们的方法是一般的，可以应用于有向或无向图，精确或近似最短的路径或可达性查询。我们使用理论和实验手段的组合研究了所提出的数据结构。我们实施了算法，并检查了来自不同应用领域的几个现实生活网络上所得数据结构的大小。我们的实验表明，标签的总尺寸通常不比网络本身大得多，并且通常比网络及其及其及其及其及其及其网络的显式表示。
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. We propose a new data structure for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v.Our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. For shortest paths, such a cover is a collection S of shortest paths such that, for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from S. We describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. Our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries.We study the proposed data structure using a combination of theoretical and experimental means. We implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. Our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.