Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
Bezaye Tesfaye (),
Nikolaus Augsten (),
Mateusz Pawlik (),
Michael H. Böhlen () and
Christian S. Jensen ()
Additional contact information
Bezaye Tesfaye: University of Salzburg
Nikolaus Augsten: University of Salzburg
Mateusz Pawlik: University of Salzburg
Michael H. Böhlen: University of Zurich
Christian S. Jensen: Aalborg University
Information Systems Frontiers, 2022, vol. 24, issue 1, No 2, 29 pages
Abstract 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.
Keywords: Reachability queries; Public transport networks; Temporal graphs; Spatial network databases (search for similar items in EconPapers)
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
http://link.springer.com/10.1007/s10796-021-10164-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:spr:infosf:v:24:y:2022:i:1:d:10.1007_s10796-021-10164-2
Ordering information: This journal article can be ordered from
Access Statistics for this article
Information Systems Frontiers is currently edited by Ram Ramesh and Raghav Rao
More articles in Information Systems Frontiers from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().