Exploring Graph Partitioning for Shortest Path Queries on Road Networks

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:add9dbed71ef6c4b19a8c0666b4d2506

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, 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> <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:rights rdf:resource="https://kops.uni-konstanz.de/page/termsofuse"/> <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>

Dateiabrufe seit 23.01.2018 (Informationen über die Zugriffsstatistik)

Chondrogiannis_2-1azm08fvlin6g6.pdf 51

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto