Document Open Access Logo

Efficient Construction of Probabilistic Tree Embeddings

Authors Guy E. Blelloch, Yan Gu, Yihan Sun

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.26.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Author Details

Guy E. Blelloch
Yan Gu
Yihan Sun

Cite As Get BibTex

Guy E. Blelloch, Yan Gu, and Yihan Sun. Efficient Construction of Probabilistic Tree Embeddings. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.26

Abstract

In this paper we describe an algorithm that embeds a graph metric (V,d_G) on an undirected weighted graph G=(V,E) into a distribution of tree metrics (T,D_T) such that for every pair u,v in V, d_G(u,v)<=d_T(u,v) and E_T[d_T(u,v)]<=O(log n)d_G(u,v).  Such embeddings have proved highly useful in designing fast approximation algorithms, as many hard problems on graphs are easy to solve on tree instances.  For a graph with n vertices and m edges, our algorithm runs in O(m log n) time with high probability, which improves the previous upper bound of O(m log^3 n) shown by Mendel et al. in 2009.

The key component of our algorithm is a new approximate single-source shortest-path algorithm, which implements the priority queue with a new data structure, the bucket-tree structure. The algorithm has three properties: it only requires linear time in terms of the number of edges in the input graph; the computed distances have the distance preserving property; and when computing the shortest-paths to the k-nearest vertices from the source, it only requires to visit these vertices and their edge lists. These properties are essential to guarantee the correctness and the stated work bound.

Using this shortest-path algorithm, we show how to generate an intermediate structure, the approximate dominance sequences of the input graph, in O(m log n) time, and further propose a simple yet efficient algorithm to converted this sequence to a tree embedding in O(n log n) time, both with high probability. Combining the three subroutines gives the stated work bound of the algorithm. 

We also show a new application of probabilistic tree embeddings: they can be used to accelerate the construction of a series of approximate distance oracles.

Subject Classification

Keywords
  • Graph Algorithm
  • Metric Embeddings
  • Probabilistic Tree Embeddings
  • Single-source Shortest-paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rachit Agarwal and Philip Godfrey. Distance oracles for stretch less than 2. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 526-538, 2013. Google Scholar
  2. Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78-100, 1995. Google Scholar
  3. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of IEEE Foundations of Computer Science (FOCS), pages 184-193, 1996. Google Scholar
  4. Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 161-168. ACM, 1998. Google Scholar
  5. Surender Baswana and Telikepalli Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pages 591-602, 2006. Google Scholar
  6. Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. Parallelism in randomized incremental algorithms. In Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 467-478, 2016. Google Scholar
  7. Guy E. Blelloch, Yan Gu, and Yihan Sun. Efficient construction of probabilistic tree embeddings. arXiv preprint arXiv:1605.04651, 2016. URL: https://arxiv.org/abs/1605.04651.
  8. Guy E. Blelloch, Anupam Gupta, and Kanat Tangwongsan. Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design. In Proceedings of ACM symposium on Parallelism in Algorithms and Architectures (SPAA), pages 205-213, 2012. Google Scholar
  9. Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. SIAM Journal on Computing, 34(2):358-372, 2005. Google Scholar
  10. Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 654-663, 2014. Google Scholar
  11. Shiri Chechik. Approximate distance oracles with improved bounds. In Proceedings of ACM on Symposium on Theory of Computing (STOC), pages 1-10, 2015. Google Scholar
  12. Edith Cohen. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55(3):441-453, 1997. Google Scholar
  13. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 47(1):132-166, 2000. Google Scholar
  14. Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly mlog^1/2n time. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 343-352, 2014. Google Scholar
  15. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  16. Michael Elkin and Seth Pettie. A linear-size logarithmic stretch path-reporting distance oracle for general graphs. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 805-821, 2015. Google Scholar
  17. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences (JCSS), 69(3):485-497, 2004. Google Scholar
  18. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3):596-615, 1987. Google Scholar
  19. Stephan Friedrichs and Christoph Lenzen. Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford. In Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 455-466, 2016. Google Scholar
  20. Harold N. Gabow. Scaling algorithms for network problems. Journal of Computer and System Sciences, 31(2):148-168, 1985. Google Scholar
  21. Mohsen Ghaffari and Christoph Lenzen. Near-optimal distributed tree embedding. In International Symposium on Distributed Computing, pages 197-211. Springer, 2014. Google Scholar
  22. Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. Distributed Computing, 25(3):189-205, 2012. Google Scholar
  23. Philip N. Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205-220, 1997. Google Scholar
  24. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pages 109-118, 2006. Google Scholar
  25. Manor Mendel and Chaya Schwob. Fast C-K-R partitions of sparse graphs. Chicago Journal of Theoretical Computer Science, pages 1-18, 2009. Article 2. URL: http://dx.doi.org/10.4086/cjtcs.2009.002.
  26. Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. In Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 192-201, 2015. Google Scholar
  27. Donald R. Morrison. PATRICIA - Practical Algorithm To Retrieve Information Coded in Alphanumeric. Journal of the ACM (JACM), 15(4):514-534, October 1968. Google Scholar
  28. Assaf Naor and Terence Tao. Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem. Israel Journal of Mathematics, 192(1):489-504, 2012. Google Scholar
  29. Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput., 34(6):1398-1431, 2005. Google Scholar
  30. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 255-264, 2008. Google Scholar
  31. Raimund Seidel. Backwards analysis of randomized geometric algorithms. Springer, 1993. Google Scholar
  32. Mikkel Thorup. Undirected single source shortest paths in linear time. In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pages 12-21, 1997. Google Scholar
  33. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  34. Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 539-549, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact