An Efficient Index for Reachability Queries in Public Transport Networks

Bezaye Tesfaye, Nikolaus Augsten, Mateusz Pawlik, Michael H. Böhlen, Christian S. JensenADBIS 2020 · OpenReview

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.

Introduction

In standard road networks, travel costs are relatively static. However, public transport networks are inherently time-dependent: the travel time between two stations depends on the departure time and the specific transit schedule. A reachability query asks: "Given a starting station and time, which points of interest (POIs) can be reached within a specific time budget?" This query is fundamental for urban planning, real estate services, and spatial recommendation systems.

Existing solutions are often inadequate for large-scale applications. A "no-index" approach using a time-dependent Dijkstra’s algorithm is computationally expensive as it explores every edge. Conversely, a "full-index" approach precomputing all-pairs shortest paths is storage-prohibitive for large cities. This research introduces a "middle ground"—a lightweight Reachability Index (RQ) that balances storage efficiency with query speed.

Methodology

The proposed Reachability Index (RQ) leverages network partitioning to simplify the search space. The construction involves four primary stages:

  1. Graph Partitioning: The network is divided into disjoint "cells" using the Louvain method, a community detection algorithm. This creates cells with high internal connectivity and sparse external connections.
  2. Identifying Border Nodes: Nodes that facilitate connections between different cells are designated as border nodes.
  3. Constructing the Index Core: The index discards internal edges in favor of:
  4. BB Edges: Direct edges between border nodes of adjacent cells.
  5. BC Edges: "Shortcut" edges representing the shortest time-dependent paths between border nodes within the same cell.
  6. POI Insertion (BP Edges): POIs are dynamically linked to the border nodes of their respective cells. This modularity allows for real-time updates to POI data without recomputing the entire index.
Overview of the reachability index construction: (a) original network, (b) partitioned graph, (c) index core, and (d) POI insertion.

Query Processing: During a query, the system searches the simplified index core. A "flagging" heuristic optimizes this process by preventing redundant explorations of a cell's internal paths if a more efficient route to its exit has already been identified.

Experimental Evaluation

The effectiveness of the RQ index was tested on three datasets:

  • Zurich: Dense real-world public transport data.
  • Berlin: Sparse real-world public transport data.
  • Synthetic: A $6 \times 6$ grid of "spider-web" subgraphs simulating clustered urban centers.

Key Results

  • Computational Efficiency: In realistic scenarios, the RQ index reduces the number of expanded edges—a proxy for computational work—by approximately one order of magnitude compared to the non-indexed Dijkstra approach.
  • Storage Scalability: The RQ index is up to four orders of magnitude smaller than a fully-indexed point-to-point approach (SP) while maintaining competitive query performance.
  • Clustered Performance: On the Synthetic dataset, the RQ index expanded up to three orders of magnitude fewer edges than the fully-indexed approach, demonstrating its strength in large, naturally clustered networks.

Insights and Discussion

The "aha moment" of this research is the shift from edge-by-edge to cell-by-cell expansion. By abstracting the internal structure of neighborhoods into high-level blocks, the search can "jump" across the network. Furthermore, the index is highly adaptable; by applying the "last-train-home" principle—retaining only the latest departure for any given arrival—the authors achieved a 70% reduction in index size.

However, the approach has limitations. Its performance is sensitive to the quality of the partitioning; poor cell boundaries can lead to suboptimal shortcuts. Additionally, in extremely sparse networks like Berlin, the number of shortcut edges can occasionally exceed the original edge count, a phenomenon termed the "sparsity penalty." Future work will focus on refining partitioning strategies and optimizing shortcut generation for sparse topologies.

Summary updated

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.
BibTeX
@inproceedings{tesfaye2020efficient,
  author = {Bezaye Tesfaye and Nikolaus Augsten and Mateusz Pawlik and Michael H. Böhlen and Christian S. Jensen},
  title = {{An Efficient Index for Reachability Queries in Public Transport Networks}},
  booktitle = {ADBIS},
  year = {2020},
  url = {https://openreview.net/forum?id=5F4C1UkH3x},
}
Figure