KOPS - The Institutional Repository of the University of Konstanz

Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing

Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

FUNKE, Stefan, Sabine STORANDT, 2015. Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing. 26th International Symposium, ISAAC 2015. Nagoya, Japan, Dec 9, 2015 - Dec 11, 2015. In: ELBASSIONI, Khaled, ed., Kazuhisa MAKINO, ed.. Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, proceedings. Heidelberg:Springer, pp. 479-490. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-662-48970-3. Available under: doi: 10.1007/978-3-662-48971-0_41

@inproceedings{Funke2015-11-27Prova-43548, title={Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing}, year={2015}, doi={10.1007/978-3-662-48971-0_41}, number={9472}, isbn={978-3-662-48970-3}, issn={0302-9743}, address={Heidelberg}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, proceedings}, pages={479--490}, editor={Elbassioni, Khaled and Makino, Kazuhisa}, author={Funke, Stefan and Storandt, Sabine} }

We present a new way of analyzing Contraction Hierarchies (CH), a widely used speed-up technique for shortest path computations in road networks. In previous work, preprocessing and query times of deterministically constructed CH on road networks with n nodes were shown to be polynomial in n as well as the highway dimension h of the network and its diameter D. While h is conjectured to be polylogarithmic for road networks, a tight bound remains an open problem. We rely on the empirically justifiable assumption of the road network exhibiting small growth. We introduce a method to construct randomized Contraction Hierarchies on road networks as well as a probabilistic query routine. Our analysis reveals that randomized CH lead to sublinear search space sizes in the order of √n logn √n, auxiliary data in the order of nlog<sup>2</sup>√n, and correct query results with high probability after a polynomial time preprocessing phase. 2018-10-16T12:21:54Z 2015-11-27 Funke, Stefan Storandt, Sabine Funke, Stefan Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing Storandt, Sabine 2018-10-16T12:21:54Z eng

This item appears in the following Collection(s)

Search KOPS


Browse

My Account