An Efficient Index for Reachability Queries in Public Transport Networks
Open Access
- 17 August 2020
- book chapter
- Published by Springer Nature
- Vol. 12245, 34-48
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
This publication has 18 references indexed in Scilit:
- Route Planning in Transportation Networks2016
- Scalable Transfer Patterns2015
- TF-Label2013
- Defining isochrones in multimodal spatial networks2011
- Group recommendationProceedings of the VLDB Endowment, 2009
- Car or Public Transport—Two Worlds2009
- Computing isochrones in multi-modal, schedule-based transport networks2008
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Reachability and Distance Queries via 2-Hop LabelsSIAM Journal on Computing, 2003
- A note on two problems in connexion with graphsNumerische Mathematik, 1959