2026-07-25T23:26:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13790 2024-03-06T10:52:58Z ddc:004 open_access

Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications Buchhold, Valentin Wagner, Dorothea Nearest neighbors points of interest travel demand generation radiation model customizable contraction hierarchies 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Valentin Buchhold and Dorothea Wagner 2021 Is Part Of LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2021.18 urn:nbn:de:0030-drops-137908 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.18 eng https://creativecommons.org/licenses/by/4.0/legalcode