Document Open Access Logo

Approximate Nearest Neighbor Search in Metrics of Planar Graphs

Authors Ittai Abraham, Shiri Chechik, Robert Krauthgamer, Udi Wieder

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.20.pdf
  • Filesize: 0.67 MB
  • 23 pages

Document Identifiers

Author Details

Ittai Abraham
Shiri Chechik
Robert Krauthgamer
Udi Wieder

Cite As Get BibTex

Ittai Abraham, Shiri Chechik, Robert Krauthgamer, and Udi Wieder. Approximate Nearest Neighbor Search in Metrics of Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 20-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.20

Abstract

We investigate the problem of approximate Nearest-Neighbor Search (NNS) in graphical metrics: The task is to preprocess an edge-weighted graph G=(V,E) on m vertices and a small "dataset" D \subset V of size n << m, so that given a query point q \in V, one can quickly approximate dist(q,D) (the distance from q to its closest vertex in D) and find a vertex a \in D within this approximated distance. We assume the query algorithm has access to a distance oracle, that quickly evaluates the exact distance between any pair of vertices.

For planar graphs G with maximum degree Delta, we show how to efficiently construct a compact data structure -- of size ~O(n(Delta+1/epsilon)) -- that answers (1+epsilon)-NNS queries in time ~O(Delta+1/epsilon). Thus, as far as NNS applications are concerned, metrics derived from bounded-degree planar graphs behave as low-dimensional metrics, even though planar metrics do not necessarily have a low doubling dimension, nor can they be embedded with low distortion into l_2. We complement our algorithmic result by lower bounds showing that the access to an exact distance oracle (rather than an approximate one) and the dependency on Delta (in query time) are both essential.

Subject Classification

Keywords
  • Data Structures
  • Nearest Neighbor Search
  • Planar Graphs
  • Planar Metrics
  • Planar Separator

Metrics

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

References

  1. Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proceedings of the 44th symposium on Theory of Computing, pages 1199-1218. ACM, 2012. Google Scholar
  2. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Hierarchical hub labelings for shortest paths. In Proceedings of the 20th Annual European conference on Algorithms, ESA'12, pages 24-35. Springer-Verlag, 2012. Google Scholar
  3. Ittai Abraham and Cyril Gavoille. Object location using path separators. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC'06, pages 188-197. ACM, 2006. Google Scholar
  4. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In 41st Annual Symposium on Foundations of Computer Science, pages 198-207, 2000. Google Scholar
  5. Eyal Amir. Approximation algorithms for treewidth. Algorithmica, 56(4):448-479, January 2010. Google Scholar
  6. Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566, 2007. Google Scholar
  7. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, September 1975. Google Scholar
  8. A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In 23rd international conference on Machine learning, pages 97-104. ACM, 2006. Google Scholar
  9. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, December 1996. Google Scholar
  10. Hans L. Bodlaender, Pal Gronas Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. An O(c^k n) 5-approximation algorithm for treewidth. In 54th Annual Symposium on Foundations of Computer Science, pages 499-508, 2013. Google Scholar
  11. Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms, 18(2):238-255, March 1995. Google Scholar
  12. R. Cole and L.-A. Gottlieb. Searching dynamic point sets in spaces with bounded doubling dimension. In 38th Annual ACM Symposium on Theory of Computing, pages 574-583. ACM, 2006. Google Scholar
  13. David Eisenstat, Philip N. Klein, and Claire Mathieu. Approximating k-center in planar graphs. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 617-627. SIAM, 2014. Google Scholar
  14. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th International Conference on Experimental Algorithms, WEA'08, pages 319-333. Springer-Verlag, 2008. Google Scholar
  15. S. Har-Peled and M. Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing, 35(5):1148-1184, 2006. Google Scholar
  16. Goos Kant and Hans L. Bodlaender. Triangulating planar graphs while minimizing the maximum degree. Inf. Comput., 135(1):1-14, May 1997. Google Scholar
  17. D. Karger and M. Ruhl. Finding nearest neighbors in growth-restricted metrics. In 34th Annual ACM Symposium on the Theory of Computing, pages 63-66, 2002. Google Scholar
  18. R. Krauthgamer and J. R. Lee. Navigating nets: Simple algorithms for proximity search. In 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 791-801, January 2004. Google Scholar
  19. R. Krauthgamer and J. R. Lee. The black-box complexity of nearest-neighbor search. Theoret. Comput. Sci., 348(2-3):262-276, 2005. Google Scholar
  20. R. Krauthgamer, H. Nguyen, and T. Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics, 28(1):127-141, 2014. Google Scholar
  21. R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177-189, 1979. Google Scholar
  22. C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory Comput. Syst., 32(3):241-280, 1999. Google Scholar
  23. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, November 2004. 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