Bezaye Tesfaye
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Bezaye Tesfaye has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Christian S. Jensen
Aalborg University
3 shared publications - Mateusz Pawlik
University of Salzburg
3 shared publications - Michael Bohlen
University of Zurich, Zurich, Switzerland
3 shared publications - Nikolaus Augsten
University of Salzburg
3 shared publications
Latest Publications
- Open Access
- 14 August 2021
- Published by Springer Nature in Information Systems Frontiers
- Vol. 24 (1) , 11-29
Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
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.
- 14 August 2021
- Published by Springer Nature in Information Systems Frontiers
- Vol. 24 (1) , 11-29
Open AccessSpeeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning
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.
- Open Access
- 17 August 2020
- Published by Springer Nature
- Vol. 12245, C1
Correction to: An Efficient Index for Reachability Queries in Public Transport Networks
The chapter was originally published without open access. With the author(s)’ decision to opt for retrospective open access the copyright of the chapter changed to © The Author(s) 2020 and the chapter is now available under a CC BY 4.0 license at link.springer.com
- 17 August 2020
- Published by Springer Nature
- Vol. 12245, C1
Open AccessCorrection to: An Efficient Index for Reachability Queries in Public Transport Networks
The chapter was originally published without open access. With the author(s)’ decision to opt for retrospective open access the copyright of the chapter changed to © The Author(s) 2020 and the chapter is now available under a CC BY 4.0 license at link.springer.com
- Open Access
- 17 August 2020
- Published by Springer Nature
- Vol. 12245, 34-48
An Efficient Index for Reachability Queries in Public Transport Networks
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.
- 17 August 2020
- Published by Springer Nature
- Vol. 12245, 34-48
Open AccessAn Efficient Index for Reachability Queries in Public Transport Networks
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.