skip to main content
10.1145/2424321.2424365acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
research-article

HLDB: location-based services in databases

Published: 06 November 2012 Publication History

Abstract

This paper introduces HLDB, the first practical system that can answer exact spatial queries on continental road networks entirely within a database. HLDB is based on hub labels (HL), the fastest point-to-point algorithm for road networks, and its queries are implemented (quite naturally) in standard SQL. Within the database, HLDB answers exact distance queries and retrieves full shortest-path descriptions in real time, even on networks with tens of millions of vertices. The basic algorithm can be extended in a natural way (still in SQL) to answer much more sophisticated queries, such as finding the ten closest fast-food restaurants. We also introduce efficient new HL-based algorithms for even harder problems, such as best via point, ride sharing, and point of interest prediction. The HLDB framework makes it easy to implement these algorithms in SQL, enabling interactive applications on continental road networks.

References

[1]
I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks. In SEA, volume 6630 of LNCS, pages 230--241, 2011.
[2]
I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical Hub Labelings for Shortest Paths. In ESA, volume 7501 of LNCS, pages 24--35, 2012.
[3]
I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In SODA, pages 782--793, 2010.
[4]
H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. In Transit to Constant Shortest-Path Queries in Road Networks. In ALENEX, pages 46--59, 2007.
[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.
[6]
Z. Chen, H. T. Shen, X. Zhou, and J. X. Yu. Monitoring Path Nearest Neighbor in Road Networks. In SIGMOD, pages 591--602, 2009.
[7]
H.-J. Cho and C.-W. Chung. An Efficient and Scalable Approach to CNN Queries in a Road Network. In VLDB, pages 865--876, 2005.
[8]
E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and Distance Queries via 2-hop Labels. SIAM J. Comput., 32:1338--1355, 2003.
[9]
D. Delling, A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. PHAST: Hardware-Accelerated Shortest Path Trees. In IPDPS, pages 921--931, 2011.
[10]
D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable Route Planning. In SEA, volume 6630 of LNCS, pages 376--387. Springer, 2011.
[11]
D. Delling, A. V. Goldberg, and R. F. Werneck. Faster Batched Shortest Paths in Road Networks. In ATMOS, volume 20 of OASIcs, pages 52--63, 2011.
[12]
D. Delling, P. Sanders, D. Schultes, and D. Wagner. Engineering Route Planning Algorithms. In Algorithmics of Large and Complex Networks, volume 5515 of LNCS, pages 117--139. 2009.
[13]
C. Demetrescu, A. V. Goldberg, and D. S. Johnson, editors. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book. 2009.
[14]
E. V. Denardo and B. L. Fox. Shortest-Route Methods: 1. Reaching, Pruning, and Buckets. Operations Research, 27(1):161--186, 1979.
[15]
E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269--271, 1959.
[16]
M. L. Fredman and R. E. Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM, 34(3):596--615, 1987.
[17]
J. Froehlich and J. Krumm. Route Prediction from Trip Observations. In SAE, 2008.
[18]
J. Gao, R. Jin, J. Zhou, J. X. Yu, X. Jiang, and T. Wang. Relational Approach for Shortest Path Discovery over Large Graphs. PVLDB, 5(4):358--369, 2011.
[19]
C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance Labeling in Graphs. Journal of Algorithms, 53:85--112, 2004.
[20]
R. Geisberger. Advanced Route Planning in Transportation Networks. PhD thesis, Karlsruhe Institute of Technology, 2011.
[21]
R. Geisberger, D. Luxen, P. Sanders, S. Neubauer, and L. Volker. Fast Detour Computation for Ride Sharing. In ATMOS, volume 14 of OASIcs, pages 88--99, 2010.
[22]
R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact Routing in Large Road Networks Using Contraction Hierarchies. Transportation Science, 46(3):388--404, 2012.
[23]
A. V. Goldberg. A Practical Shortest Path Algorithm with Linear Expected Time. SIAM Journal on Computing, 37:1637--1655, 2008.
[24]
A. V. Goldberg and C. Harrelson. Computing the Shortest Path: A* Search Meets Graph Theory. In SODA, pages 156--165, 2005.
[25]
A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for A*: Shortest Path Algorithms with Preprocessing. In Demetrescu et al. {13}, pages 93--139.
[26]
M. Hilger, E. Köhler, R. H. Möhring, and H. Schilling. Fast Point-to-Point Shortest Path Computations with Arc-Flags. In Demetrescu et al. {13}, pages 41--72.
[27]
G. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. ACM Transactions on Database Systems, 24:265--318, 1999.
[28]
S. Knopp, P. Sanders, D. Schultes, F. Schulz, and D. Wagner. Computing Many-to-Many Shortest Paths Using Highway Hierarchies. In ALENEX, pages 36--45, 2007.
[29]
J. Krumm. Real Time Destination Prediction Based on Efficient Routes. In SAE, 2006.
[30]
D. Papadias, A. Zhang, N. Mamoulis, and Y. Tao. Query Processing in Spatial Network Databases. In VLDB, pages 802--813, 2003.
[31]
PTV AG - Planung Transport Verkehr, 1979.
[32]
P. Sanders and D. Schultes. Engineering Highway Hierarchies. In ESA, volume 4168 of LNCS, pages 804--816, 2006.
[33]
P. Sanders, D. Schultes, and C. Vetter. Mobile Route Planning. In ESA, volume 5193 of LNCS, pages 732--743, 2008.
[34]
J. Sankaranarayanan, H. Alborzi, and H. Samet. Efficient Query Processing on Spatial Networks. In GIS, pages 200--209, 2005.
[35]
J. Sankaranarayanan and H. Samet. Query Processing Using Distance Oracles for Spatial Networks. IEEE Transactions on Knowledge and Data Engineering, 22(8):1158--1175, 2010.
[36]
J. Sankaranarayanan and H. Samet. Roads Belong in Databases. IEEE Data Engineering Bulletin, 33(2):4--11, 2010.
[37]
J. Sankaranarayanan, H. Samet, and H. Alborzi. Path Oracles for Spatial Networks. In VLDB, pages 1210--1221, 2009.
[38]
R. Schenkel, A. Theobald, and G. Weikum. HOPI: An Efficient Connection Index for Complex XML Document Collections. In EDBT, volume 2992 of LNCS, pages 237--255, 2004.

Cited By

View all
  • (2023)The Partition Bridge (PB) tree: Efficient nearest neighbor query processing on road networksInformation Systems10.1016/j.is.2023.102256118(102256)Online publication date: Sep-2023
  • (2019)Shortest Feasible Paths with Charging Stops for Battery Electric VehiclesTransportation Science10.1287/trsc.2018.088953:6(1627-1655)Online publication date: 1-Nov-2019
  • (2018)DOSProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274898(199-208)Online publication date: 6-Nov-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems
November 2012
642 pages
ISBN:9781450316910
DOI:10.1145/2424321
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2012

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. SQL
  2. databases
  3. large road networks
  4. location services

Qualifiers

  • Research-article

Conference

SIGSPATIAL'12
Sponsor:

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)The Partition Bridge (PB) tree: Efficient nearest neighbor query processing on road networksInformation Systems10.1016/j.is.2023.102256118(102256)Online publication date: Sep-2023
  • (2019)Shortest Feasible Paths with Charging Stops for Battery Electric VehiclesTransportation Science10.1287/trsc.2018.088953:6(1627-1655)Online publication date: 1-Nov-2019
  • (2018)DOSProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274898(199-208)Online publication date: 6-Nov-2018
  • (2018)A Survey of Physics-Based Attack Detection in Cyber-Physical SystemsACM Computing Surveys10.1145/320324551:4(1-36)Online publication date: 25-Jul-2018
  • (2017)Algorithmic and hardness results for the hub labeling problemProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039780(1442-1461)Online publication date: 16-Jan-2017
  • (2017)Hub Labels on the database for large-scale graphs with the COLD frameworkGeoinformatica10.1007/s10707-016-0287-521:4(703-732)Online publication date: 1-Oct-2017
  • (2016)CDOProceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2996913.2996921(1-4)Online publication date: 31-Oct-2016
  • (2016)ReHubACM Journal of Experimental Algorithmics10.1145/299019221(1-35)Online publication date: 4-Nov-2016
  • (2016)Highway Dimension and Provably Efficient Shortest Path AlgorithmsJournal of the ACM10.1145/298547363:5(1-26)Online publication date: 8-Dec-2016
  • (2016)Customizable Contraction HierarchiesACM Journal of Experimental Algorithmics10.1145/288684321(1-49)Online publication date: 5-Apr-2016
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media