research-article

Free access

Fast shortest-path distance queries on road networks by pruned highway labeling

Authors:

Takuya Akiba,

Yoichi Iwata,

Ken-ichi Kawarabayashi,

Yuki KawataAuthors Info & Claims

Proceedings of the Meeting on Algorithm Engineering & Expermiments

Pages 147 - 154

Published: 05 January 2014 Publication History

PDF eReader

Abstract

We propose a new labeling method for shortest-path and distance queries on road networks. We present a new framework (i.e. data structure and query algorithm) referred to as highway-based labelings and a preprocessing algorithm for it named pruned highway labeling.

Our proposed method has several appealing features from different aspects in the literature. Indeed, we take advantages of theoretical analysis of the seminal result by Thorup for distance oracles, more detailed structures of real road networks, and the pruned labeling algorithm that conducts pruned Dijkstra's algorithm.

The experimental results show that the proposed method is comparable to the previous state-of-the-art labeling method in both query time and in data size, while our main improvement is that the preprocessing time is much faster.

References

[1]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In SEA, pages 230--241, 2011.

Crossref

Google Scholar

[2]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In ESA, pages 24--35, 2012.

Crossref

Google Scholar

[3]

T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD, pages 349--360, 2013.

Crossref

Google Scholar

[4]

H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. In transit to constant time shortest-path queries in road networks. In ALENEX, pages 46--59, 2007.

Crossref

Google Scholar

[5]

R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm. ACM Journal of Experimental Algorithmics, 15(2.3):1--31, 2010.

Crossref

Google Scholar

[6]

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning. In SEA, pages 376--387, 2011.

Crossref

Google Scholar

[7]

D. Delling, A. V. Goldberg, and R. F. Werneck. Hub label compression. In SEA, pages 18--29, 2013.

Google Scholar

[8]

C. Demetrescu, A. V. Goldberg, and D. S. Johnson. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74. AMS, 2009.

Google Scholar

[9]

R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA, pages 319--333, 2008.

Crossref

Google Scholar

[10]

M. Hilger, E. Köhler, R. H. Möhring, and H. Schilling. Fast point-to-point shortest path computations with arc-flags. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, 74:41--72, 2009.

Google Scholar

[11]

T. Ikeda, M. Y. Hsu, H. Imai, S. Nishimura, H. Shimoura, T. Hashimoto, K. Tenmoku, and K. Mitoh. A fast algorithm for finding better routes by ai search techniques. In VNSI, pages 291--296, 1994.

Google Scholar

[12]

M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993--1024, 2004.

Crossref

Google Scholar

[13]

Y. Yano, T. Akiba, Y. Iwata, and Y. Yoshida. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In CIKM, pages 1601--1606, 2013.

Crossref

Google Scholar

Cited By

View all

Zhang JYuan LLi WQin LZhang Y(2022)Efficient label-constrained shortest path queries on road networksProceedings of the VLDB Endowment10.14778/3494124.349414815:3(686-698)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494148
Li LCheema MAli MLu HTaniar D(2020)Continuously monitoring alternative shortest paths on road networksProceedings of the VLDB Endowment10.14778/3407790.340782213:12(2243-2255)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407822
Zhang YYu JMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Hub Labeling for Shortest Path CountingProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389737(1813-1828)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389737
Show More Cited By

Index Terms

Fast shortest-path distance queries on road networks by pruned highway labeling

Recommendations

Fast exact shortest-path distance queries on large networks by pruned landmark labeling
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search from every vertex. Seemingly too obvious and too inefficient at first ...
Shortest path and distance queries on road networks: towards bridging theory and practice
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Given two locations s and t in a road network, a distance query returns the minimum network distance from s to t, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find important ...
Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks
PACMMOD

Answering the shortest-path distance between two arbitrary locations is a fundamental problem in road networks. Labelling-based solutions are the current state-of-the-arts to render fast response time, which can generally be categorised into hub-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the Meeting on Algorithm Engineering & Expermiments

January 2014

165 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 2014

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
401
Total Downloads

Downloads (Last 12 months)130
Downloads (Last 6 weeks)9

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang JYuan LLi WQin LZhang Y(2022)Efficient label-constrained shortest path queries on road networksProceedings of the VLDB Endowment10.14778/3494124.349414815:3(686-698)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494148
Li LCheema MAli MLu HTaniar D(2020)Continuously monitoring alternative shortest paths on road networksProceedings of the VLDB Endowment10.14778/3407790.340782213:12(2243-2255)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407822
Zhang YYu JMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Hub Labeling for Shortest Path CountingProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389737(1813-1828)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389737
Li WQiao MQin LZhang YChang LLin XBoncz PManegold SAilamaki ADeshpande AKraska T(2019)Scaling Distance Labeling on Small-World NetworksProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319877(1060-1077)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319877
Ouyang DQin LChang LLin XZhang YZhu QDas GJermaine CBernstein P(2018)When Hierarchy Meets 2-Hop-LabelingProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3196913(709-724)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3196913
Li YU LYiu MKou N(2018)An experimental study on hub labeling based shortest path algorithmsProceedings of the VLDB Endowment10.1145/3164135.316414111:4(445-457)Online publication date: 5-Oct-2018
Li YU LYiu MKou N(2017)An experimental study on hub labeling based shortest path algorithmsProceedings of the VLDB Endowment10.1145/3186728.316414111:4(445-457)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1145/3186728.3164141
Abeywickrama TCheema MTaniar D(2016)k-nearest neighbors on road networksProceedings of the VLDB Endowment10.14778/2904121.29041259:6(492-503)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.14778/2904121.2904125
Efentakis APfoser D(2016)ReHubACM Journal of Experimental Algorithmics10.1145/299019221(1-35)Online publication date: 4-Nov-2016
https://dl.acm.org/doi/10.1145/2990192
Akiba TYano YMizuno NMukhopadhyay SZhai CBertino ECrestani FMostafa JTang JSi LZhou XChang YLi YSondhi P(2016)Hierarchical and Dynamic k-Path CoversProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983712(1543-1552)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2983323.2983712
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Fast exact shortest-path distance queries on large networks by pruned landmark labeling

Shortest path and distance queries on road networks: towards bridging theory and practice

Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations