Online Landmark-Based Batch Processing of Shortest Path Queries
Online Landmark-Based Batch Processing of Shortest Path Queries
Loading...
Date
2021
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
International patent number
Link to the license
EU project number
Project
Open Access publication
Collections
Title in another language
Publication type
Contribution to a conference collection
Publication status
Published
Published in
Scientific and Statistical Database Management : 33rd International Conference, SSDBM 2021, Tampa, Florida, USA, July 6 - 7, 2021, proceedings / Zhu, Qiang et al. (ed.). - New York, USA : ACM, 2021. - pp. 133-144. - ISBN 978-1-4503-8413-1
Abstract
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.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Conference
SSDBM 2021: 33rd International Conference on Scientific and Statistical Database Management, Jul 6, 2021 - Jul 7, 2021, Tampa, Florida, USA
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690
HOTZ, 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, Jul 6, 2021 - Jul 7, 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, pp. 133-144. ISBN 978-1-4503-8413-1. Available under: doi: 10.1145/3468791.3468844BibTex
@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>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes