Online Landmark-Based Batch Processing of Shortest Path Queries

被引:2
作者
Hotz, Manuel [1 ]
Chondrogiannis, Theodoros [1 ]
Woerteler, Leonard [1 ]
Grossniklaus, Michael [1 ]
机构
[1] Univ Konstanz, Constance, Germany
来源
33RD INTERNATIONAL CONFERENCE ON SCIENTIFIC AND STATISTICAL DATABASE MANAGEMENT (SSDBM 2021) | 2020年
关键词
Batch Processing; Landmark Embedding; Shortest Paths; HIERARCHIES;
D O I
10.1145/3468791.3468844
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Processing shortest path queries is a basic operation in many graph problems. Both preprocessing-based and batch processing techniques have been proposed to speed up the computation of a single shortest path by amortizing its costs. However, both of these approaches suffer from limitations. The former techniques are prohibitively expensive in situations where the precomputed information needs to be updated frequently due to changes in the graph, while the latter require coordinates and cannot be used on non-spatial graphs. In this paper, we address both limitations and propose novel techniques for batch processing shortest paths queries using landmarks. We show how preprocessing can be avoided entirely by integrating the computation of landmark distances into query processing. Our experimental results demonstrate that our techniques outperform the state of the art on both spatial and non-spatial graphs with a maximum speedup of 3.61x in online scenarios.
引用
收藏
页码:133 / 144
页数:12
相关论文
共 34 条
  • [1] [Anonymous], 2006, P INT S ADV GEOGR IN, DOI DOI 10.1145/1183471.1183506
  • [2] [Anonymous], 2008, Proc. of SIGMOD'08
  • [3] [Anonymous], 2005, In Proc
  • [4] Bast H, 2016, LECT NOTES COMPUT SC, V9220, P19, DOI 10.1007/978-3-319-49487-6_2
  • [5] Chondrogiannis Theodoros, 2016, 2016 17th IEEE International Conference on Mobile Data Management (MDM), P242, DOI 10.1109/MDM.2016.45
  • [6] Cohen L, 2018, PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, P1427
  • [7] Demetrescu C., 2006, 9th DIMACS implementation challenge-shortest paths
  • [8] Dijkstra E. W., 1959, NUMER MATH, V1, P1, DOI DOI 10.1007/BF01386390
  • [9] ECML/PKDD 2015 Competition, 2015, ECML PKDD 15 TAX TRA
  • [10] Edelkamp S, 2012, HEURISTIC SEARCH: THEORY AND APPLICATIONS, P47