License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.18
URN: urn:nbn:de:0030-drops-137908
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13790/
Buchhold, Valentin ;
Wagner, Dorothea
Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications
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.
BibTeX - Entry
@InProceedings{buchhold_et_al:LIPIcs.SEA.2021.18,
author = {Buchhold, Valentin and Wagner, Dorothea},
title = {{Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {18:1--18:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13790},
URN = {urn:nbn:de:0030-drops-137908},
doi = {10.4230/LIPIcs.SEA.2021.18},
annote = {Keywords: Nearest neighbors, points of interest, travel demand generation, radiation model, customizable contraction hierarchies}
}
