KIT | KIT-Bibliothek | Impressum | Datenschutz

Nearest-neighbor queries in customizable contraction hierarchies and applications

Buchhold, Valentin; Wagner, Dorothea


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000135204
Veröffentlicht am 12.07.2021
DOI: 10.4230/LIPIcs.SEA.2021.18
Zitationen: 2
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597718-5-6
ISSN: 1868-8969
KITopen-ID: 1000135204
Erschienen in 19th International Symposium on Experimental Algorithms (SEA 2021). Ed.: D. Coudert
Veranstaltung 19th International Symposium on Experimental Algorithms (SEA 2021), Nizza, Frankreich, 07.06.2021 – 09.06.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 18
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 190
Schlagwörter Nearest neighbors, points of interest, travel demand generation, radiation model, customizable contraction hierarchies
Nachgewiesen in Scopus
Globale Ziele für nachhaltige Entwicklung Ziel 11 – Nachhaltige Städte und Gemeinden
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page