Customizable Hub Labeling : Properties and Algorithms

Blum, Johannes; Storandt, Sabine

Customizable Hub Labeling : Properties and Algorithms

Files

There are no files associated with this item.

Date

2022

Publication type

Contribution to a conference collection

Publication status

Published

Published in

Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings / Zhang, Yong; Miao, Dongjing; Möhring, Rolf (ed.). - Cham : Springer, 2022. - (Lecture Notes in Computer Science ; 13595). - pp. 345-356

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 O(log²n)-approximation algorithm for the average label size, and propose efficient customization algorithms.

Subject (DDC)

004 Computer Science

Keywords

Route planning, Hub labeling, Customization

Conference

Computing and Combinatorics - 28th International Conference, COCOON 2022, Oct 22, 2022 - Oct 24, 2022, Shenzhen, China

Cite This

ISO 690

BLUM, Johannes, Sabine STORANDT, 2022. Customizable Hub Labeling : Properties and Algorithms. Computing and Combinatorics - 28th International Conference, COCOON 2022. Shenzhen, China, Oct 22, 2022 - Oct 24, 2022. In: ZHANG, Yong, ed., Dongjing MIAO, ed., Rolf MÖHRING, ed.. Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings. Cham:Springer, pp. 345-356. Available under: doi: 10.1007/978-3-031-22105-7\_31

BibTex

@inproceedings{Blum2022Custo-59727,
  year={2022},
  doi={10.1007/978-3-031-22105-7\_31},
  title={Customizable Hub Labeling : Properties and Algorithms},
  number={13595},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings},
  pages={345--356},
  editor={Zhang, Yong and Miao, Dongjing and Möhring, Rolf},
  author={Blum, Johannes and Storandt, Sabine}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/59727">
    <dc:contributor>Blum, Johannes</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/59727"/>
    <dcterms:title>Customizable Hub Labeling : Properties and Algorithms</dcterms:title>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-16T12:18:46Z</dc:date>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">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 O(log&lt;sup&gt;2&lt;/sup&gt;n)-approximation algorithm for the average label size, and propose efficient customization algorithms.</dcterms:abstract>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:creator>Blum, Johannes</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2022</dcterms:issued>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-16T12:18:46Z</dcterms:available>
    <dc:language>eng</dc:language>
    <dc:creator>Storandt, Sabine</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
  </rdf:Description>
</rdf:RDF>

Bibliography of Konstanz

Yes