Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning

Area of Science:

• Computer Science
• Database Systems
• Spatial Databases

Background:

• Public transport networks present unique challenges for pathfinding due to time-varying travel costs.
• Reachability queries, crucial for applications like recommendations and geomarketing, retrieve all points of interest (POIs) accessible within a budget.
• Existing methods, such as modified Dijkstra's algorithm or individual path queries per POI, lack scalability for large networks.

Purpose of the Study:

• To develop an efficient and scalable solution for reachability queries in time-dependent public transport networks.
• To propose a novel index that optimizes the retrieval of reachable POIs.

Main Methods:

• A new lightweight reachability index is proposed.
• The core strategy involves partitioning the transport network into cells.
• The query process expands the network analysis cell by cell, differing from traditional edge-by-edge approaches.

Main Results:

• The proposed index-based approach significantly enhances the efficiency of reachability queries.
• Empirical evaluations on both synthetic and real-world datasets demonstrate the effectiveness of the method.
• The solution scales well for large public transport networks.

Conclusions:

• The novel cell-based reachability index offers an efficient and effective solution for querying public transport networks.
• This approach overcomes the scalability limitations of existing methods.
• The findings have implications for various location-based services and spatial data analysis applications.