Finding k-shortest paths with limited overlap

Lade...
Vorschaubild
Dateien
Chondrogiannis_2-76tlg703mdvs7.pdf
Chondrogiannis_2-76tlg703mdvs7.pdfGröße: 2.55 MBDownloads: 201
Datum
2020
Autor:innen
Bouros, Panagiotis
Gamper, Johann
Leser, Ulf
Blumenthal, David B.
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Link zur Lizenz
EU-Projektnummer
DFG-Projektnummer
Angaben zur Forschungsförderung (Freitext)
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
The VLDB Journal. Springer. 2020, 29(5), pp. 1023-1047. ISSN 1066-8888. eISSN 0949-877X. Available under: doi: 10.1007/s00778-020-00604-x
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.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690CHONDROGIANNIS, Theodoros, Panagiotis BOUROS, Johann GAMPER, Ulf LESER, David B. BLUMENTHAL, 2020. Finding k-shortest paths with limited overlap. In: The VLDB Journal. Springer. 2020, 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>
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
Ja
Begutachtet
Ja
Diese Publikation teilen