An Efficient Index for Reachability Queries in Public Transport Networks

Bezaye Tesfaye, Nikolaus Augsten, Mateusz Pawlik, Michael Hanspeter Böhlen, Christian S. Jensen

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)
18 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationADBIS 2020: Advances in Databases and Information Systems
EditorsJérôme Darmont, Boris Novikov, Robert Wrembel
Number of pages15
PublisherSpringer
Publication date2020
Pages34-48
ISBN (Print)978-3-030-54831-5
ISBN (Electronic)978-3-030-54832-2
DOIs
Publication statusPublished - 2020
EventEuropean Conference on Advances in Databases and Information Systems 2020 - Lyon, France
Duration: 25 Aug 202027 Aug 2020

Conference

ConferenceEuropean Conference on Advances in Databases and Information Systems 2020
Country/TerritoryFrance
CityLyon
Period25/08/202027/08/2020
SeriesLecture Notes in Computer Science (LNCS)
Volume12245
ISSN0302-9743

Keywords

  • Public transport networks
  • Reachability queries
  • Spatial network databases
  • Temporal graphs

Fingerprint

Dive into the research topics of 'An Efficient Index for Reachability Queries in Public Transport Networks'. Together they form a unique fingerprint.

Cite this