Exploring Graph Partitioning for Shortest Path Queries on Road Networks

Cite This

Files in this item

Checksum: 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, 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>

Downloads since Jan 23, 2018 (Information about access statistics)

Chondrogiannis_2-1azm08fvlin6g6.pdf 66

This item appears in the following Collection(s)

Search KOPS


Browse

My Account