Document Open Access Logo

Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications

Authors Valentin Buchhold, Dorothea Wagner

PDF

File

Thumbnail PDF
PDF
LIPIcs.SEA.2021.18.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Nearest neighbor algorithms
  • Applied computing → Transportation
Keywords
  • Nearest neighbors
  • points of interest
  • travel demand generation
  • radiation model
  • customizable contraction hierarchies

Metrics

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

Abstract

Customizable contraction hierarchies are one of the most popular route planning frameworks in practice, due to their simplicity and versatility. In this work, we present a novel algorithm for finding k-nearest neighbors in customizable contraction hierarchies by systematically exploring the associated separator decomposition tree. Compared to previous bucket-based approaches, our algorithm requires much less target-dependent preprocessing effort. Moreover, we use our novel approach in two concrete applications. The first application are online k-closest point-of-interest queries, where the points of interest are only revealed at query time. We achieve query times of about 25 milliseconds on a continental road network, which is fast enough for interactive systems. The second application is travel demand generation. We show how to accelerate a recently introduced travel demand generator by a factor of more than 50 using our novel nearest-neighbor algorithm.

Cite As Get BibTex

Valentin Buchhold and Dorothea Wagner. Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.18

Author Details

Valentin Buchhold
  • Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology, Germany

Supplementary Materials

References

  1. Tenindra Abeywickrama and Muhammad Aamir Cheema. Efficient landmark-based candidate generation for kNN queries on road networks. In K. Selçuk Candan, Lei Chen, Torben Bach Pedersen, Lijun Chang, and Wen Hua, editors, Proceedings of the 22nd International Conference on Database Systems for Advanced Applications (DASFAA'17), volume 10178 of Lecture Notes in Computer Science, pages 425-440. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-55699-4_26.
  2. Tenindra Abeywickrama, Muhammad Aamir Cheema, and David Taniar. K-nearest neighbors on road networks: A journey in experimentation and in-memory implementation. Proceedings of the VLDB Endowment, 9(6):492-503, 2016. URL: https://doi.org/10.14778/2904121.2904125.
  3. Takuya Akiba, Yoichi Iwata, Ken ichi Kawarabayashi, and Yuki Kawata. Fast shortest-path distance queries on road networks by pruned highway labeling. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX'14), pages 147-154. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973198.14.
  4. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
  5. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645:112-127, 2016. URL: https://doi.org/10.1016/j.tcs.2016.07.003.
  6. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-optimal routes for electric vehicles. In Craig A. Knoblock, Peer Kröger, John Krumm, Markus Schneider, and Peter Widmayer, editors, Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL'13), pages 54-63. ACM Press, 2013. URL: https://doi.org/10.1145/2525314.2525361.
  7. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975. URL: https://doi.org/10.1145/361002.361007.
  8. Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Efficient calculation of microscopic travel demand data with low calibration effort. In Farnoush Banaei-Kashani, Goce Trajcevski, Ralf Hartmut Güting, Lars Kulik, and Shawn D. Newsam, editors, Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL'19), pages 379-388. ACM Press, 2019. URL: https://doi.org/10.1145/3347146.3359361.
  9. Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-time traffic assignment using engineered customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 24(2):2.4:1-2.4:28, 2019. URL: https://doi.org/10.1145/3362693.
  10. Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. Customizable contraction hierarchies with turn costs. In Dennis Huisman and Christos D. Zaroliagis, editors, Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'20), volume 85 of OpenAccess Series in Informatics (OASIcs), pages 9:1-9:15. Schloss Dagstuhl, 2020. URL: https://doi.org/10.4230/OASIcs.ATMOS.2020.9.
  11. Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing, 73(7):940-952, 2013. URL: https://doi.org/10.1016/j.jpdc.2012.02.007.
  12. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566-591, 2017. URL: https://doi.org/10.1287/trsc.2014.0579.
  13. Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster batched shortest paths in road networks. In Alberto Caprara and Spyros C. Kontogiannis, editors, Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11), volume 20 of OpenAccess Series in Informatics (OASIcs), pages 52-63. Schloss Dagstuhl, 2011. URL: https://doi.org/10.4230/OASIcs.ATMOS.2011.52.
  14. Daniel Delling and Renato F. Werneck. Customizable point-of-interest queries in road networks. IEEE Transactions on Knowledge and Data Engineering, 27(3):686-698, 2015. URL: https://doi.org/10.1109/TKDE.2014.2345386.
  15. Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book. American Mathematical Society, 2009. Google Scholar
  16. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 21(1):1.5:1-1.5:49, 2016. URL: https://doi.org/10.1145/2886843.
  17. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  18. Alexandros Efentakis and Dieter Pfoser. GRASP. Extending graph separators for the single-source shortest-path problem. In Andreas S. Schulz and Dorothea Wagner, editors, Proceedings of the 22th Annual European Symposium on Algorithms (ESA'14), volume 8737 of Lecture Notes in Computer Science, pages 358-370. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_30.
  19. Alexandros Efentakis, Dieter Pfoser, and Yannis Vassiliou. SALT. A unified framework for all shortest-path query variants on road networks. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), volume 9125 of Lecture Notes in Computer Science, pages 298-311. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_23.
  20. Jochen Eisner, Stefan Funke, Andre Herbst, Andreas Spillner, and Sabine Storandt. Algorithms for matching and predicting trajectories. In Matthias Müller-Hannemann and Renato F. Werneck, editors, Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX'11), pages 84-95. SIAM, 2011. URL: https://doi.org/10.1137/1.9781611972917.9.
  21. Jerome H. Friedman, Jon Louis Bentley, and Raphael A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3):209-226, 1977. URL: https://doi.org/10.1145/355744.355745.
  22. Robert Geisberger. Advanced Route Planning in Transportation Networks. PhD thesis, Karlsruhe Institute of Technology, 2011. URL: https://doi.org/10.5445/IR/1000021997.
  23. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, 2012. URL: https://doi.org/10.1287/trsc.1110.0401.
  24. Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. URL: https://doi.org/10.1137/0710032.
  25. Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl, and Dorothea Wagner. Faster and better nested dissection orders for customizable contraction hierarchies. Algorithms, 12(9):1-20, 2019. URL: https://doi.org/10.3390/a12090196.
  26. Antonin Guttman. R-trees: A dynamic index structure for spatial searching. ACM SIGMOD Record, 14(2):47-57, 1984. URL: https://doi.org/10.1145/602259.602266.
  27. Michael Hamann and Ben Strasser. Graph bisection with pareto optimization. ACM Journal of Experimental Algorithmics, 23(1):1.2:1-1.2:34, 2018. URL: https://doi.org/10.1145/3173045.
  28. Donald B. Johnson. Priority queues with update and finding minimum spanning trees. Information Processing Letters, 4(3):53-57, 1975. URL: https://doi.org/10.1016/0020-0190(75)90001-0.
  29. Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. Computing many-to-many shortest paths using highway hierarchies. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07), pages 36-45. SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.4.
  30. Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker. Evolution and evaluation of the penalty method for alternative graphs. In Daniele Frigioni and Sebastian Stiller, editors, Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'13), volume 33 of OpenAccess Series in Informatics (OASIcs), pages 94-107. Schloss Dagstuhl, 2013. URL: https://doi.org/10.4230/OASIcs.ATMOS.2013.94.
  31. Ken C. K. Lee, Wang-Chien Lee, and Baihua Zheng. Fast object search on road networks. In Martin L. Kersten, Boris Novikov, Jens Teubner, Vladimir Polutin, and Stefan Manegold, editors, Proceedings of the 12th International Conference on Extending Database Technology (EDBT'09), pages 1018-1029. ACM Press, 2009. URL: https://doi.org/10.1145/1516360.1516476.
  32. Ken C. K. Lee, Wang-Chien Lee, Baihua Zheng, and Yuan Tian. ROAD: A new spatial object search framework for road networks. IEEE Transactions on Knowledge and Data Engineering, 24(3):547-560, 2012. URL: https://doi.org/10.1109/TKDE.2010.243.
  33. Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. Query processing in spatial network databases. In Johann-Christoph Freytag, Peter C. Lockemann, Serge Abiteboul, Michael J. Carey, Patricia G. Selinger, and Andreas Heuer, editors, Proceedings of the 29th International Conference on Very Large Data Bases (VLDB'03), pages 802-813. Morgan Kaufmann, 2003. Google Scholar
  34. Hanan Samet, Jagan Sankaranarayanan, and Houman Alborzi. Scalable network distance browsing in spatial databases. In Jason Tsong-Li Wang, editor, Proceedings of the 27th ACM SIGMOD International Conference on Management of Data (SIGMOD'08), pages 43-54. ACM Press, 2008. URL: https://doi.org/10.1145/1376616.1376623.
  35. Jagan Sankaranarayanan, Houman Alborzi, and Hanan Samet. Efficient query processing on spatial networks. In Cyrus Shahabi and Omar Boucelma, editors, Proceedings of the 13th ACM International Workshop on Geographic Information Systems (GIS'05), pages 200-209. ACM Press, 2005. URL: https://doi.org/10.1145/1097064.1097093.
  36. Aaron Schild and Christian Sommer. On balanced separators in road networks. In Evripidis Bampis, editor, Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), volume 9125 of Lecture Notes in Computer Science, pages 286-297. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-20086-6_22.
  37. Filippo Simini, Marta C. González, Amos Maritan, and Albert-László Barabási. A universal model for mobility and migration patterns. Nature, 484(7392):96-100, 2012. URL: https://doi.org/10.1038/nature10856.
  38. Filippo Simini, Amos Maritan, and Zoltán Néda. Human mobility in a continuum approach. PLOS ONE, 8(3):1-8, 2013. URL: https://doi.org/10.1371/journal.pone.0060069.
  39. Ruicheng Zhong, Guoliang Li, Kian-Lee Tan, and Lizhu Zhou. G-tree: An efficient index for KNN search on road networks. In Qi He, Arun Iyengar, Wolfgang Nejdl, Jian Pei, and Rajeev Rastogi, editors, Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM'13), pages 39-48. ACM Press, 2013. URL: https://doi.org/10.1145/2505515.2505749.
  40. Ruicheng Zhong, Guoliang Li, Kian-Lee Tan, Lizhu Zhou, and Zhiguo Gong. G-tree: An efficient and scalable index for spatial search on road networks. IEEE Transactions on Knowledge and Data Engineering, 27(8):2175-2189, 2015. URL: https://doi.org/10.1109/TKDE.2015.2399306.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact