Finding k-shortest paths with limited overlap

Chondrogiannis, Theodoros; Bouros, Panagiotis; Gamper, Johann; Leser, Ulf; Blumenthal, David B.

Finding k-shortest paths with limited overlap

Dateien

Chondrogiannis_2-76tlg703mdvs7.pdf(2.55 MB)

Datum

2020

Autor:innen

Chondrogiannis, Theodoros

Bouros, Panagiotis

Gamper, Johann

Leser, Ulf

Blumenthal, David B.

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

The VLDB Journal ; 29 (2020), 5. - S. 1023-1047. - Springer. - ISSN 1066-8888. - eISSN 0949-877X

Zusammenfassung

In this paper, we investigate the computation of alternative paths between two locations in a road network. More specifically, we study the k-shortest paths with limited overlap (kSPwLO kSPwLO ) problem that aims at finding a set of k paths such that all paths are sufficiently dissimilar to each other and as short as possible. To compute kSPwLO kSPwLO queries, we propose two exact algorithms, termed OnePass and MultiPass, and we formally prove that MultiPass is optimal in terms of complexity. We also study two classes of heuristic algorithms: (a) performance-oriented heuristic algorithms that trade shortness for performance, i.e., they reduce query processing time, but do not guarantee that the length of each subsequent result is minimum; and (b) completeness-oriented heuristic algorithms that trade dissimilarity for completeness, i.e., they relax the similarity constraint to return a result that contains exactly k paths. An extensive experimental analysis on real road networks demonstrates the efficiency of our proposed solutions in terms of runtime and quality of the result.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

CHONDROGIANNIS, Theodoros, Panagiotis BOUROS, Johann GAMPER, Ulf LESER, David B. BLUMENTHAL, 2020. Finding k-shortest paths with limited overlap. In: The VLDB Journal. Springer. 29(5), pp. 1023-1047. ISSN 1066-8888. eISSN 0949-877X. Available under: doi: 10.1007/s00778-020-00604-x

BibTex

@article{Chondrogiannis2020-09Findi-49276,
  year={2020},
  doi={10.1007/s00778-020-00604-x},
  title={Finding k-shortest paths with limited overlap},
  number={5},
  volume={29},
  issn={1066-8888},
  journal={The VLDB Journal},
  pages={1023--1047},
  author={Chondrogiannis, Theodoros and Bouros, Panagiotis and Gamper, Johann and Leser, Ulf and Blumenthal, David B.}
}

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/49276">
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/49276/1/Chondrogiannis_2-76tlg703mdvs7.pdf"/>
    <dc:contributor>Bouros, Panagiotis</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-04-23T13:01:36Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Gamper, Johann</dc:contributor>
    <dc:creator>Gamper, Johann</dc:creator>
    <dc:language>eng</dc:language>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/49276/1/Chondrogiannis_2-76tlg703mdvs7.pdf"/>
    <dc:creator>Chondrogiannis, Theodoros</dc:creator>
    <dcterms:title>Finding k-shortest paths with limited overlap</dcterms:title>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-04-23T13:01:36Z</dc:date>
    <dc:contributor>Chondrogiannis, Theodoros</dc:contributor>
    <dc:creator>Blumenthal, David B.</dc:creator>
    <dc:contributor>Leser, Ulf</dc:contributor>
    <dc:rights>Attribution 4.0 International</dc:rights>
    <dc:creator>Bouros, Panagiotis</dc:creator>
    <dc:contributor>Blumenthal, David B.</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/49276"/>
    <dc:creator>Leser, Ulf</dc:creator>
    <dcterms:issued>2020-09</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:abstract xml:lang="eng">In this paper, we investigate the computation of alternative paths between two locations in a road network. More specifically, we study the k-shortest paths with limited overlap (kSPwLO kSPwLO ) problem that aims at finding a set of k paths such that all paths are sufficiently dissimilar to each other and as short as possible. To compute kSPwLO kSPwLO queries, we propose two exact algorithms, termed OnePass and MultiPass, and we formally prove that MultiPass is optimal in terms of complexity. We also study two classes of heuristic algorithms: (a) performance-oriented heuristic algorithms that trade shortness for performance, i.e., they reduce query processing time, but do not guarantee that the length of each subsequent result is minimum; and (b) completeness-oriented heuristic algorithms that trade dissimilarity for completeness, i.e., they relax the similarity constraint to return a result that contains exactly k paths. An extensive experimental analysis on real road networks demonstrates the efficiency of our proposed solutions in terms of runtime and quality of the result.</dcterms:abstract>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/4.0/"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja

Begutachtet

Ja