Exploring Graph Partitioning for Shortest Path Queries on Road Networks
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
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
Computing the shortest path between two locations in a road network is an important problem that has found numerous applications. The classic solution for the problem is Dijkstra’s algorithm [1]. Although simple and elegant, the algorithm has proven to be inefficient for very large road networks. To address this deficiency of Dijkstra’s algorithm, a plethora of techniques that introduce some preprocessing to reduce the query time have been proposed. In this paper, we propose Partition-based Shortcuts (PbS), a technique based on graph-partitioning which offers fast query processing and supports efficient edge weight updates. We present a shortcut computation scheme, which exploits the traits of a graph partition. We also present a modified version of the bidirectional search [2], which uses the precomputed shortcuts to efficiently answer shortest path queries. Moreover, we introduce the Corridor Matrix (CM), a partition-based structure which is exploited to reduce the search space during the processing of shortest path queries when the source and the target point are close. Finally, we evaluate the performance of our modified algorithm in terms of preprocessing cost and query runtime for various graph partitioning configurations.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
CHONDROGIANNIS, Theodoros, Johann GAMPER, 2014. Exploring Graph Partitioning for Shortest Path Queries on Road Networks. 26th GI-Workshop Grundlagen von Datenbanken : GvDB '14. Bozen, Italy, 21. Okt. 2014 - 24. Okt. 2014. In: KLAN, Friederike, ed. and others. Proceedings of the 26th GI-Workshop Grundlagen von Datenbanken. 2014, pp. 71-76. CEUR Workshop Proceedings. 1313. eISSN 1613-0073BibTex
@inproceedings{Chondrogiannis2014Explo-41122, year={2014}, title={Exploring Graph Partitioning for Shortest Path Queries on Road Networks}, url={http://ceur-ws.org/Vol-1313/paper_13.pdf}, number={1313}, series={CEUR Workshop Proceedings}, booktitle={Proceedings of the 26th GI-Workshop Grundlagen von Datenbanken}, pages={71--76}, editor={Klan, Friederike}, author={Chondrogiannis, Theodoros and Gamper, Johann} }
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/41122"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Chondrogiannis, Theodoros</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41122"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-23T15:34:39Z</dc:date> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-23T15:34:39Z</dcterms:available> <dc:creator>Gamper, Johann</dc:creator> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:abstract xml:lang="eng">Computing the shortest path between two locations in a road network is an important problem that has found numerous applications. The classic solution for the problem is Dijkstra’s algorithm [1]. Although simple and elegant, the algorithm has proven to be inefficient for very large road networks. To address this deficiency of Dijkstra’s algorithm, a plethora of techniques that introduce some preprocessing to reduce the query time have been proposed. In this paper, we propose Partition-based Shortcuts (PbS), a technique based on graph-partitioning which offers fast query processing and supports efficient edge weight updates. We present a shortcut computation scheme, which exploits the traits of a graph partition. We also present a modified version of the bidirectional search [2], which uses the precomputed shortcuts to efficiently answer shortest path queries. Moreover, we introduce the Corridor Matrix (CM), a partition-based structure which is exploited to reduce the search space during the processing of shortest path queries when the source and the target point are close. Finally, we evaluate the performance of our modified algorithm in terms of preprocessing cost and query runtime for various graph partitioning configurations.</dcterms:abstract> <dcterms:issued>2014</dcterms:issued> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/41122/3/Chondrogiannis_2-1azm08fvlin6g6.pdf"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:rights>terms-of-use</dc:rights> <dc:language>eng</dc:language> <dc:contributor>Gamper, Johann</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/41122/3/Chondrogiannis_2-1azm08fvlin6g6.pdf"/> <dcterms:title>Exploring Graph Partitioning for Shortest Path Queries on Road Networks</dcterms:title> <dc:creator>Chondrogiannis, Theodoros</dc:creator> </rdf:Description> </rdf:RDF>