On hierarchical routing in doubling metrics
We study the problem of routing in doubling metrics and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a metric (X, d) has doubling dimension dim(X) at most α if every ball can be covered by 2α balls of half its radius. (A doubling metric is one whose doubling dimension dim(X) is a constant.) We consider the metric space induced by the shortest-path distance in an underlying undirected graph G. We show how to perform (1 + τ)-stretch routing on such a metric for any 0 < τ ≤ 1 with routing tables of size at most (α/τ)O(α) log log δ bits with only (α/τ)O(α) log entries, where is the diameter of the graph, and δ is the maximum degree of the graph G; hence, the number of routing table entries is just τ−O(1) log for doubling metrics. These results extend and improve on those of Talwar (2004). We also give better constructions of sparse spanners for doubling metrics than those obtained from the routing tables earlier; for τ > 0, we give algorithms to construct (1 + τ)-stretch spanners for a metric (X, d) with maximum degree at most (2 + 1/τ)O(dim(X)), matching the results of Das et al. for Euclidean metrics.
Duke Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Related Subject Headings
- Computation Theory & Mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 4605 Data management and data science
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
Citation
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Related Subject Headings
- Computation Theory & Mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 4605 Data management and data science
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics