Publikation:

Online Landmark-Based Batch Processing of Shortest Path Queries

Lade...
Vorschaubild

Dateien

Hotz_2-dlxcombd5sa19.pdf
Hotz_2-dlxcombd5sa19.pdfGröße: 2.28 MBDownloads: 203

Datum

2021

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

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

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

ZHU, Qiang, ed. and others. Scientific and Statistical Database Management : 33rd International Conference, SSDBM 2021, Tampa, Florida, USA, July 6 - 7, 2021, proceedings. New York, USA: ACM, 2021, pp. 133-144. ISBN 978-1-4503-8413-1. Available under: doi: 10.1145/3468791.3468844

Zusammenfassung

Processing shortest path queries is a basic operation in many graph problems. Both preprocessing-based and batch processing techniques have been proposed to speed up the computation of a single shortest path by amortizing its costs. However, both of these approaches suffer from limitations. The former techniques are prohibitively expensive in situations where the precomputed information needs to be updated frequently due to changes in the graph, while the latter require coordinates and cannot be used on non-spatial graphs. In this paper, we address both limitations and propose novel techniques for batch processing shortest paths queries using landmarks. We show how preprocessing can be avoided entirely by integrating the computation of landmark distances into query processing. Our experimental results demonstrate that our techniques outperform the state of the art on both spatial and non-spatial graphs with a maximum speedup of 3.61 × in online scenarios.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

SSDBM 2021: 33rd International Conference on Scientific and Statistical Database Management, 6. Juli 2021 - 7. Juli 2021, Tampa, Florida, USA
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690HOTZ, Manuel, Theodoros CHONDROGIANNIS, Leonard WÖRTELER, Michael GROSSNIKLAUS, 2021. Online Landmark-Based Batch Processing of Shortest Path Queries. SSDBM 2021: 33rd International Conference on Scientific and Statistical Database Management. Tampa, Florida, USA, 6. Juli 2021 - 7. Juli 2021. In: ZHU, Qiang, ed. and others. Scientific and Statistical Database Management : 33rd International Conference, SSDBM 2021, Tampa, Florida, USA, July 6 - 7, 2021, proceedings. New York, USA: ACM, 2021, pp. 133-144. ISBN 978-1-4503-8413-1. Available under: doi: 10.1145/3468791.3468844
BibTex
@inproceedings{Hotz2021Onlin-54785,
  year={2021},
  doi={10.1145/3468791.3468844},
  title={Online Landmark-Based Batch Processing of Shortest Path Queries},
  isbn={978-1-4503-8413-1},
  publisher={ACM},
  address={New York, USA},
  booktitle={Scientific and Statistical Database Management : 33rd International Conference, SSDBM 2021, Tampa, Florida, USA, July 6 - 7, 2021, proceedings},
  pages={133--144},
  editor={Zhu, Qiang},
  author={Hotz, Manuel and Chondrogiannis, Theodoros and Wörteler, Leonard and Grossniklaus, Michael}
}
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/54785">
    <dc:language>eng</dc:language>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-09-02T12:50:25Z</dcterms:available>
    <dcterms:issued>2021</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-09-02T12:50:25Z</dc:date>
    <dc:contributor>Hotz, Manuel</dc:contributor>
    <dc:creator>Wörteler, Leonard</dc:creator>
    <dc:rights>terms-of-use</dc:rights>
    <dc:contributor>Grossniklaus, Michael</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Chondrogiannis, Theodoros</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Chondrogiannis, Theodoros</dc:contributor>
    <dc:creator>Grossniklaus, Michael</dc:creator>
    <dc:creator>Hotz, Manuel</dc:creator>
    <dc:contributor>Wörteler, Leonard</dc:contributor>
    <dcterms:abstract xml:lang="eng">Processing shortest path queries is a basic operation in many graph problems. Both preprocessing-based and batch processing techniques have been proposed to speed up the computation of a single shortest path by amortizing its costs. However, both of these approaches suffer from limitations. The former techniques are prohibitively expensive in situations where the precomputed information needs to be updated frequently due to changes in the graph, while the latter require coordinates and cannot be used on non-spatial graphs. In this paper, we address both limitations and propose novel techniques for batch processing shortest paths queries using landmarks. We show how preprocessing can be avoided entirely by integrating the computation of landmark distances into query processing. Our experimental results demonstrate that our techniques outperform the state of the art on both spatial and non-spatial graphs with a maximum speedup of 3.61 × in online scenarios.</dcterms:abstract>
    <dcterms:title>Online Landmark-Based Batch Processing of Shortest Path Queries</dcterms:title>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/54785/1/Hotz_2-dlxcombd5sa19.pdf"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/54785"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/54785/1/Hotz_2-dlxcombd5sa19.pdf"/>
  </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
Diese Publikation teilen