Skip to main content
SpringerLink
Log in

Customizable Hub Labeling: Properties and Algorithms

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13595))

Included in the following conference series:

  • 798 Accesses

Abstract

Hub Labeling (HL) is a state-of-the-art preprocessing-based technique for route planning in road networks. It is a special incarnation of distance labeling, and it is well-studied in both theory and practice. The core concept of HL is to associate a label with each vertex, which consists of a subset of all vertices and respective shortest path information, such that the shortest path distance between any two vertices can be derived from considering the intersection of their labels. HL provides excellent query times but requires a time-consuming preprocessing phase. Therefore, in case of edge cost changes, rerunning the whole preprocessing is not viable. Inspired by the concept of Customizable Route Planning, we hence propose in this paper a Customizable Hub Labeling variant for which the edge costs in the network do not need to be known at construction time. These labels can then be used with any edge costs after conducting a so called customization phase. We study the theoretical properties of Customizable Hub Labelings, provide an \(\mathcal {O}(\log ^2 n)\)-approximation algorithm for the average label size, and propose efficient customization algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 69.99
Price excludes VAT (USA)
Softcover Book
USD 89.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Note that in [7], it was stated that the average search space size of any CCH is \(S_{\textrm{avg}}\ge {2}/{9} \cdot b_{{1}/{2}}\). The presented proof claimed that after removing a minimum \({2}/{3}\)-balanced separator, a connected component of size \(n' \ge n/3\) remains. We are however only guaranteed that \(n' \ge \lfloor n/3 \rfloor \), which yields \(S_{\textrm{avg}}\ge {1}/{12} \cdot b_{{1}/{2}}\).

References

  1. Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths in road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 230–241. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20662-7_20

    Chapter  Google Scholar 

  2. Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 24–35. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_4

    Chapter  Google Scholar 

  3. Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Ross, K.A., Srivastava, D., Papadias, D. (eds.) Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD 2013), pp. 349–360. ACM (2013). https://doi.org/10.1145/2463676.2465315

  4. Akiba, T., Iwata, Y., Yoshida, Y.: Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In: Chung, C., Broder, A.Z., Shim, K., Suel, T. (eds.) Proceedings of the 23rd International Conference on World Wide Web (WWW 2014), pp. 237–248. ACM (2014). https://doi.org/10.1145/2566486.2568007

  5. Babenko, M., Goldberg, A.V., Kaplan, H., Savchenko, R., Weller, M.: On the complexity of hub labeling (extended abstract). In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 62–74. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48054-0_6

    Chapter  MATH  Google Scholar 

  6. Bauer, R., Columbus, T., Rutter, I., Wagner, D.: Search-space size in contraction hierarchies. Theor. Comput. Sci. 645, 112–127 (2016). https://doi.org/10.1016/j.tcs.2016.07.003

    Article  MathSciNet  MATH  Google Scholar 

  7. Blum, J., Storandt, S.: Lower bounds and approximation algorithms for search space sizes in contraction hierarchies. In: Grandoni, F., Herman, G., Sanders, P. (eds.) Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020). LIPIcs, vol. 173, pp. 20:1–20:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ESA.2020.20

  8. Chen, Z., Fu, A.W., Jiang, M., Lo, E., Zhang, P.: P2H: efficient distance querying on road networks by projected vertex separators. In: Li, G., Li, Z., Idreos, S., Srivastava, D. (eds.) Proceedings of the 2021 International Conference on Management of Data (SIGMOD 2021), pp. 313–325. ACM (2021). https://doi.org/10.1145/3448016.3459245

  9. Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338–1355 (2003). https://doi.org/10.1137/S0097539702403098

    Article  MathSciNet  MATH  Google Scholar 

  10. D’angelo, G., D’emidio, M., Frigioni, D.: Fully dynamic 2-hop cover labeling. ACM J. Exp. Algorithmics 24(1), 1–36 (2019). https://doi.org/10.1145/3299901

    Article  MathSciNet  MATH  Google Scholar 

  11. Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376–387. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20662-7_32

    Chapter  Google Scholar 

  12. Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Robust distance queries on massive networks. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 321–333. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44777-2_27

    Chapter  Google Scholar 

  13. Delling, D., Goldberg, A.V., Savchenko, R., Werneck, R.F.: Hub labels: theory and practice. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 259–270. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07959-2_22

    Chapter  Google Scholar 

  14. Delling, D., Goldberg, A.V., Werneck, R.F.: Hub label compression. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 18–29. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38527-8_4

    Chapter  Google Scholar 

  15. Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. ACM J. Exp. Algorithmics 21(1), 1–49 (2016). https://doi.org/10.1145/2886843

    Article  MathSciNet  MATH  Google Scholar 

  16. Farhan, M., Wang, Q.: Efficient maintenance of distance labelling for incremental updates in large dynamic graphs. In: Velegrakis, Y., Zeinalipour-Yazti, D., Chrysanthis, P.K., Guerra, F. (eds.) Proceedings of the 24th International Conference on Extending Database Technology (EDBT 2021), pp. 385–390. OpenProceedings.org (2021). https://doi.org/10.5441/002/edbt.2021.39

  17. Farhan, M., Wang, Q., Lin, Yu., McKay, B.: Fast fully dynamic labelling for distance queries. VLDB J. 31, 483–506 (2021). https://doi.org/10.1007/s00778-021-00707-z

    Article  Google Scholar 

  18. Feige, U., Mahdian, M.: Finding small balanced separators. In: Kleinberg, J.M. (ed.) Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006), pp. 375–384. ACM (2006). https://doi.org/10.1145/1132516.1132573

  19. Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388–404 (2012). https://doi.org/10.1287/trsc.1110.0401

    Article  Google Scholar 

  20. Leighton, F.T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), pp. 422–431. IEEE Computer Society (1988). https://doi.org/10.1109/SFCS.1988.21958

  21. Ouyang, D., Qin, L., Chang, L., Lin, X., Zhang, Y., Zhu, Q.: When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks. In: Das, G., Jermaine, C.M., Bernstein, P.A. (eds.) Proceedings of the 2018 International Conference on Management of Data (SIGMOD 2018), pp. 709–724. ACM (2018). https://doi.org/10.1145/3183713.3196913

  22. Rupp, T., Funke, S.: A lower bound for the query phase of contraction hierarchies and hub labels and a provably optimal instance-based schema. Algorithms 14(6), 164 (2021). https://doi.org/10.3390/a14060164

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Konstanz, Konstanz, Germany

    Johannes Blum & Sabine Storandt

Authors
  1. Johannes Blum
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sabine Storandt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Johannes Blum .

Editor information

Editors and Affiliations

  1. Shenzhen Institute of Advanced Technology, Shenzhen, China

    Yong Zhang

  2. Harbin Institute of Technology, Harbin, China

    Dongjing Miao

  3. Technical University of Berlin, Berlin, Germany

    Rolf Möhring

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Blum, J., Storandt, S. (2022). Customizable Hub Labeling: Properties and Algorithms. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-22105-7_31

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-22104-0

  • Online ISBN: 978-3-031-22105-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation