Publikation:

ParDiSP : A Partition-Based Framework for Distance and Shortest Path Queries on Road Networks

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2016

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

CHOW, Chi-Yin, ed. and others. Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM) : Volume 1. Piscataway, NJ: IEEE, 2016, pp. 242-251. eISSN 2375-0324. ISBN 978-1-5090-0883-4. Available under: doi: 10.1109/MDM.2016.45

Zusammenfassung

To process shortest path and distance queries on road networks, various preprocessing techniques have been proposed. State-of-the-art methods for distance queries offer superior query time but do not provide any efficient retrieval mechanism for the shortest path. In contrast, state-of-the-art methods for shortest path queries show relatively poor performance for distance queries. In this paper, we propose a Partition-based framework for Distance and Shortest Path queries (ParDiSP), which efficiently supports both types of queries. After partitioning a road network into components, ParDiSP precomputes the distances between any node in a component and the border nodes of the same component, the pair wise distances between all border nodes, and the union of the shortest paths between all border nodes. For query processing, ParDiSP runs the ALT algorithm for both distance and shortest path queries if source and target are located in the same component. Otherwise, ParDiSP answers distance queries by combining distances from exactly three precomputed distance tables. For shortest path queries, the information in the distance tables allows to identify two border nodes that are traversed by the shortest path, thereby decomposing the path into three segments which can be computed in parallel. A detailed experimental evaluation shows that ParDiSP outperforms two state-of-the-art solutions for shortest path queries and is comparable to the state-of-the-art for distance queries. For mixed query loads containing both distance and shortest path queries, ParDiSP outperforms a combination of the best methods for each query type, while its space requirements are significantly smaller.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

17th IEEE International Conference on Mobile Data Management (MDM), 13. Juni 2016 - 16. Juni 2016, Porto, Portugal
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CHONDROGIANNIS, Theodoros, Johann GAMPER, 2016. ParDiSP : A Partition-Based Framework for Distance and Shortest Path Queries on Road Networks. 17th IEEE International Conference on Mobile Data Management (MDM). Porto, Portugal, 13. Juni 2016 - 16. Juni 2016. In: CHOW, Chi-Yin, ed. and others. Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM) : Volume 1. Piscataway, NJ: IEEE, 2016, pp. 242-251. eISSN 2375-0324. ISBN 978-1-5090-0883-4. Available under: doi: 10.1109/MDM.2016.45
BibTex
@inproceedings{Chondrogiannis2016-06ParDi-41135,
  year={2016},
  doi={10.1109/MDM.2016.45},
  title={ParDiSP : A Partition-Based Framework for Distance and Shortest Path Queries on Road Networks},
  isbn={978-1-5090-0883-4},
  publisher={IEEE},
  address={Piscataway, NJ},
  booktitle={Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM) : Volume 1},
  pages={242--251},
  editor={Chow, Chi-Yin},
  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/41135">
    <dc:contributor>Chondrogiannis, Theodoros</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-24T14:43:30Z</dcterms:available>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-01-24T14:43:30Z</dc:date>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Gamper, Johann</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Gamper, Johann</dc:contributor>
    <dcterms:title>ParDiSP : A Partition-Based Framework for Distance and Shortest Path Queries on Road Networks</dcterms:title>
    <dcterms:abstract xml:lang="eng">To process shortest path and distance queries on road networks, various preprocessing techniques have been proposed. State-of-the-art methods for distance queries offer superior query time but do not provide any efficient retrieval mechanism for the shortest path. In contrast, state-of-the-art methods for shortest path queries show relatively poor performance for distance queries. In this paper, we propose a Partition-based framework for Distance and Shortest Path queries (ParDiSP), which efficiently supports both types of queries. After partitioning a road network into components, ParDiSP precomputes the distances between any node in a component and the border nodes of the same component, the pair wise distances between all border nodes, and the union of the shortest paths between all border nodes. For query processing, ParDiSP runs the ALT algorithm for both distance and shortest path queries if source and target are located in the same component. Otherwise, ParDiSP answers distance queries by combining distances from exactly three precomputed distance tables. For shortest path queries, the information in the distance tables allows to identify two border nodes that are traversed by the shortest path, thereby decomposing the path into three segments which can be computed in parallel. A detailed experimental evaluation shows that ParDiSP outperforms two state-of-the-art solutions for shortest path queries and is comparable to the state-of-the-art for distance queries. For mixed query loads containing both distance and shortest path queries, ParDiSP outperforms a combination of the best methods for each query type, while its space requirements are significantly smaller.</dcterms:abstract>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41135"/>
    <dc:language>eng</dc:language>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:issued>2016-06</dcterms:issued>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Chondrogiannis, Theodoros</dc:creator>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen