Cargando…

Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning

Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost...

Descripción completa

Detalles Bibliográficos
Autores principales: Tesfaye, Bezaye, Augsten, Nikolaus, Pawlik, Mateusz, Böhlen, Michael H., Jensen, Christian S.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8924103/
https://www.ncbi.nlm.nih.gov/pubmed/35310777
http://dx.doi.org/10.1007/s10796-021-10164-2
_version_ 1784669774923431936
author Tesfaye, Bezaye
Augsten, Nikolaus
Pawlik, Mateusz
Böhlen, Michael H.
Jensen, Christian S.
author_facet Tesfaye, Bezaye
Augsten, Nikolaus
Pawlik, Mateusz
Böhlen, Michael H.
Jensen, Christian S.
author_sort Tesfaye, Bezaye
collection PubMed
description Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost budget. Reachability queries are essential building blocks in many applications, for example, group recommendations, ranking spatial queries, or geomarketing. We propose an efficient solution for reachability queries in public transport networks. Currently, there are two options to solve reachability queries. (1) Execute a modified version of Dijkstra’s algorithm that supports time-dependent edge traversal costs; this solution is slow since it must expand edge by edge and does not use an index. (2) Issue a separate path query for each single POI, i.e., a single reachability query requires answering many path queries. None of these solutions scales to large networks with many POIs. We propose a novel and lightweight reachability index. The key idea is to partition the network into cells. Then, in contrast to other approaches, we expand the network cell by cell. Empirical evaluations on synthetic and real-world networks confirm the efficiency and the effectiveness of our index-based reachability query solution.
format Online
Article
Text
id pubmed-8924103
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Springer US
record_format MEDLINE/PubMed
spelling pubmed-89241032022-03-17 Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning Tesfaye, Bezaye Augsten, Nikolaus Pawlik, Mateusz Böhlen, Michael H. Jensen, Christian S. Inf Syst Front Article Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost budget. Reachability queries are essential building blocks in many applications, for example, group recommendations, ranking spatial queries, or geomarketing. We propose an efficient solution for reachability queries in public transport networks. Currently, there are two options to solve reachability queries. (1) Execute a modified version of Dijkstra’s algorithm that supports time-dependent edge traversal costs; this solution is slow since it must expand edge by edge and does not use an index. (2) Issue a separate path query for each single POI, i.e., a single reachability query requires answering many path queries. None of these solutions scales to large networks with many POIs. We propose a novel and lightweight reachability index. The key idea is to partition the network into cells. Then, in contrast to other approaches, we expand the network cell by cell. Empirical evaluations on synthetic and real-world networks confirm the efficiency and the effectiveness of our index-based reachability query solution. Springer US 2021-08-14 2022 /pmc/articles/PMC8924103/ /pubmed/35310777 http://dx.doi.org/10.1007/s10796-021-10164-2 Text en © The Author(s) 2021 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Article
Tesfaye, Bezaye
Augsten, Nikolaus
Pawlik, Mateusz
Böhlen, Michael H.
Jensen, Christian S.
Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
title Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
title_full Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
title_fullStr Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
title_full_unstemmed Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
title_short Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
title_sort speeding up reachability queries in public transport networks using graph partitioning
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8924103/
https://www.ncbi.nlm.nih.gov/pubmed/35310777
http://dx.doi.org/10.1007/s10796-021-10164-2
work_keys_str_mv AT tesfayebezaye speedingupreachabilityqueriesinpublictransportnetworksusinggraphpartitioning
AT augstennikolaus speedingupreachabilityqueriesinpublictransportnetworksusinggraphpartitioning
AT pawlikmateusz speedingupreachabilityqueriesinpublictransportnetworksusinggraphpartitioning
AT bohlenmichaelh speedingupreachabilityqueriesinpublictransportnetworksusinggraphpartitioning
AT jensenchristians speedingupreachabilityqueriesinpublictransportnetworksusinggraphpartitioning