Customizable Hub Labeling : Properties and Algorithms

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2022
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
ZHANG, Yong, ed., Dongjing MIAO, ed., Rolf MÖHRING, ed.. Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings. Cham: Springer, 2022, pp. 345-356. Lecture Notes in Computer Science. 13595. Available under: doi: 10.1007/978-3-031-22105-7\_31
Zusammenfassung

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

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Route planning, Hub labeling, Customization
Konferenz
Computing and Combinatorics - 28th International Conference, COCOON 2022, 22. Okt. 2022 - 24. Okt. 2022, Shenzhen, China
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BLUM, Johannes, Sabine STORANDT, 2022. Customizable Hub Labeling : Properties and Algorithms. Computing and Combinatorics - 28th International Conference, COCOON 2022. Shenzhen, China, 22. Okt. 2022 - 24. Okt. 2022. In: ZHANG, Yong, ed., Dongjing MIAO, ed., Rolf MÖHRING, ed.. Computing and Combinatorics : 28th International Conference, COCOON 2022, Proceedings. Cham: Springer, 2022, pp. 345-356. Lecture Notes in Computer Science. 13595. 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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen