Back to Search
Start Over
Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
- Source :
- Tesfaye, B, Augsten, N, Pawlik, M, Böhlen, M H & Jensen, C S 2022, ' Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning ', Information Systems Frontiers, vol. 24, no. 1, pp. 11–29 . https://doi.org/10.1007/s10796-021-10164-2
- Publication Year :
- 2022
-
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.
- Subjects :
- Spatial network databases
Temporal graphs
Theoretical computer science
Computer Networks and Communications
Computer science
10009 Department of Informatics
Node (networking)
Graph partition
000 Computer science, knowledge & systems
1710 Information Systems
Theoretical Computer Science
Ranking (information retrieval)
1712 Software
Tree traversal
Reachability
Path (graph theory)
Shortest path problem
1705 Computer Networks and Communications
Reachability queries
2614 Theoretical Computer Science
Dijkstra's algorithm
Software
Public transport networks
Information Systems
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Tesfaye, B, Augsten, N, Pawlik, M, Böhlen, M H & Jensen, C S 2022, ' Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning ', Information Systems Frontiers, vol. 24, no. 1, pp. 11–29 . https://doi.org/10.1007/s10796-021-10164-2
- Accession number :
- edsair.doi.dedup.....ad0a94a2e37f1d350f65aaa2f10c9a07