Faster Approximate Distance Queries and Compact Routing in Sparse Graphs
Faster Approximate Distance Queries and Compact Routing in Sparse Graphs
复制标题
稀疏图中更快的近似距离查询和紧凑路由
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Sariel Har
中科院分区：
文献类型：
--
作者：
R. Agarwal;Brighten Godfrey;Sariel Har
距离预言机是图的最短距离矩阵的紧凑表示。它可以被查询以近似任何一对顶点之间的最短路径。任何返回最坏情况拉伸（2k-1）的路径的距离预言机必须为n个节点的图需要空间$\Omega（n^{1 + 1/k}）$。然而，强制这个下限的困难情况是平均度为\Omega（n^{1/k}）的相当密集的图。
我们提出的距离预言，稀疏图，大大打破了下限障碍的代价是更高的查询时间。对于任何1 \leq \alpha \leq n，我们的距离预言机可以使用O（m + n^2/\alpha）空间返回拉伸2条路径，并使用O（m + n^2/\alpha ^2）空间拉伸3条路径，以O（\alpha m/n）查询时间为代价。通过设置适当的\alpha值，我们得到第一个距离预言机，其大小与图的大小成线性关系，并在非平凡查询时间内返回常数拉伸路径。查询时间可以进一步减少到O（\alpha），通过为我们所有的距离预言机使用额外的O（m \alpha）空间，或者以一个小的常数加法拉伸为代价。
我们使用我们的拉伸2距离预言机，提出了第一个紧凑的路由方案与最坏情况的拉伸2。任何紧凑的路由方案，拉伸小于2必须在某些节点上，即使是稀疏图的线性内存，因此，我们的计划，实现了最佳的拉伸与非平凡的内存需求。此外，支持大规模的模拟图，包括AS级互联网图，我们认为，我们的拉伸2计划将是简单而有效的实现作为一个分布式紧凑的路由协议。
A distance oracle is a compact representation of the shortest distance matrix of a graph. It can be queried to approximate shortest paths between any pair of vertices. Any distance oracle that returns paths of worst-case stretch (2k-1) must require space $\Omega(n^{1 + 1/k})$ for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree \Omega(n^{1/k}).
We present distance oracles that, for sparse graphs, substantially break the lower bound barrier at the expense of higher query time. For any 1 \leq \alpha \leq n, our distance oracles can return stretch 2 paths using O(m + n^2/\alpha) space and stretch 3 paths using O(m + n^2/\alpha^2) space, at the expense of O(\alpha m/n) query time. By setting appropriate values of \alpha, we get the first distance oracles that have size linear in the size of the graph, and return constant stretch paths in non-trivial query time. The query time can be further reduced to O(\alpha), by using an additional O(m \alpha) space for all our distance oracles, or at the cost of a small constant additive stretch.
We use our stretch 2 distance oracle to present the first compact routing scheme with worst-case stretch 2. Any compact routing scheme with stretch less than 2 must require linear memory at some nodes even for sparse graphs; our scheme, hence, achieves the optimal stretch with non-trivial memory requirements. Moreover, supported by large-scale simulations on graphs including the AS-level Internet graph, we argue that our stretch-2 scheme would be simple and efficient to implement as a distributed compact routing protocol.