Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Hub Labeling and A* are two well-established algorithms for shortest path computation in large graphs. Hub Labeling offers excellent query times for distance computation, but at the cost of a high space consumption for label storage. Landmark-based A* search requires less space but answers queries much slower. Recently, Landmark Hub Labeling (LHL) has been proposed, which combines both concepts and achieves a smaller space consumption than Hub Labeling and also much better query times than A*. However, the known algorithms for computing a LHL do not scale to large graphs, limiting its applicability. In this paper, we devise novel algorithms for LHL construction that work on graphs with millions of edges. We also further improve the LHL query answering algorithm and investigate how to reduce the space consumption of labeling techniques by performing bounded suboptimal pathfinding. In an extensive experimental study, we demonstrate the effectiveness of our methods and illuminate that sensible trade-offs between space consumption, query time, and path quality can be achieved with LHL.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
STORANDT, Sabine, 2024. Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding. 33rd International Joint Conference on Artificial Intelligence (IJCAI-24). Jeju, South Korea, 3. Aug. 2024 - 9. Aug. 2024. In: LARSON, Kate, Hrsg.. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. IJCAI, 2024, S. 6788-6795. ISBN 978-1-956792-04-1. Verfügbar unter: doi: 10.24963/ijcai.2024/750BibTex
@inproceedings{Storandt2024-08Scala-71117, year={2024}, doi={10.24963/ijcai.2024/750}, title={Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding}, isbn={978-1-956792-04-1}, publisher={IJCAI}, booktitle={Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence}, pages={6788--6795}, editor={Larson, Kate}, author={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/71117"> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-11-05T14:06:42Z</dc:date> <dcterms:abstract>Hub Labeling and A* are two well-established algorithms for shortest path computation in large graphs. Hub Labeling offers excellent query times for distance computation, but at the cost of a high space consumption for label storage. Landmark-based A* search requires less space but answers queries much slower. Recently, Landmark Hub Labeling (LHL) has been proposed, which combines both concepts and achieves a smaller space consumption than Hub Labeling and also much better query times than A*. However, the known algorithms for computing a LHL do not scale to large graphs, limiting its applicability. In this paper, we devise novel algorithms for LHL construction that work on graphs with millions of edges. We also further improve the LHL query answering algorithm and investigate how to reduce the space consumption of labeling techniques by performing bounded suboptimal pathfinding. In an extensive experimental study, we demonstrate the effectiveness of our methods and illuminate that sensible trade-offs between space consumption, query time, and path quality can be achieved with LHL.</dcterms:abstract> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:title>Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:contributor>Storandt, Sabine</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2024-08</dcterms:issued> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-11-05T14:06:42Z</dcterms:available> <dc:creator>Storandt, Sabine</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/71117"/> <dc:language>eng</dc:language> </rdf:Description> </rdf:RDF>