Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können am Montag, 6.2. und Dienstag, 7.2. keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted on Monday, Feb. 6 and Tuesday, Feb. 7.)
Type of Publication: | Contribution to a conference collection |
Publication status: | Published |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-2-1azm08fvlin6g6 |
Author: | Chondrogiannis, Theodoros; Gamper, Johann |
Year of publication: | 2014 |
Conference: | 26th GI-Workshop Grundlagen von Datenbanken : GvDB '14, Oct 21, 2014 - Oct 24, 2014, Bozen, Italy |
Published in: | Proceedings of the 26th GI-Workshop Grundlagen von Datenbanken / Klan, Friederike et al. (ed.). - (CEUR Workshop Proceedings ; 1313). - pp. 71-76. - eISSN 1613-0073 |
URL of original publication: | http://ceur-ws.org/Vol-1313/paper_13.pdf, Last access on Jan 23, 2018 |
Summary: |
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.
|
Subject (DDC): | 004 Computer Science |
Keywords: | Shortest path, road networks, graph partitioning |
Link to License: | In Copyright |
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, Oct 21, 2014 - Oct 24, 2014. In: KLAN, Friederike, ed. and others. Proceedings of the 26th GI-Workshop Grundlagen von Datenbanken, pp. 71-76. eISSN 1613-0073
@inproceedings{Chondrogiannis2014Explo-41122, title={Exploring Graph Partitioning for Shortest Path Queries on Road Networks}, url={http://ceur-ws.org/Vol-1313/paper_13.pdf}, year={2014}, 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 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/rdf/resource/123456789/41122"> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/41122/3/Chondrogiannis_2-1azm08fvlin6g6.pdf"/> <dc:contributor>Gamper, Johann</dc:contributor> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:language>eng</dc:language> <dcterms:issued>2014</dcterms:issued> <dc:creator>Chondrogiannis, Theodoros</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-23T15:34:39Z</dc:date> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41122"/> <dcterms:title>Exploring Graph Partitioning for Shortest Path Queries on Road Networks</dcterms:title> <dc:contributor>Chondrogiannis, Theodoros</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Gamper, Johann</dc:creator> <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> <dc:rights>terms-of-use</dc:rights> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/41122/3/Chondrogiannis_2-1azm08fvlin6g6.pdf"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-23T15:34:39Z</dcterms:available> </rdf:Description> </rdf:RDF>
Chondrogiannis_2-1azm08fvlin6g6.pdf | 207 |