Publikation:

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

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

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

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