Incremental maintenance of all-pairs shortest paths in relational DBMSs

被引：1
作者：
Greco S. [1 ]
Molinaro C. [1 ]
Pulice C. [2 ]
Quintana X. [2 ]
机构：
[1] University of Calabria, Rende
[2] University of Maryland, College Park, MD
来源：
Social Network Analysis and Mining | 2017年 / 7卷 / 1期
关键词：
Incremental algorithms; Relational databases; Shortest distances; Shortest paths;
D O I：
10.1007/s13278-017-0457-y
中图分类号：
学科分类号：
摘要：
Computing shortest paths is a classical graph theory problem and a central task in many applications. Although many algorithms to solve this problem have been proposed over the years, they are designed to work in the main memory and/or with static graphs, which limits their applicability to many current applications where graphs are highly dynamic, that is, subject to frequent updates. In this paper, we propose novel efficient incremental algorithms for maintaining all-pairs shortest paths and distances in dynamic graphs. We experimentally evaluate our approach on several real-world datasets, showing that it significantly outperforms current algorithms designed for the same problem. © 2017, Springer-Verlag GmbH Austria.
引用
收藏
相关论文
共 41 条
  • [1] Akiba T., Iwata Y., Yoshida Y., Fast exact shortest-path distance queries on large networks by pruned landmark labeling, Proceeding of international conference on management of data (SIGMOD), pp. 349-360, (2013)
  • [2] Baswana S., Hariharan R., Sen S., Maintaining all-pairs approximate shortest paths under deletion of edges, Proceedings of ACM-SIAM symposium on discrete algorithms (SODA, pp. 394-403, (2003)
  • [3] Bernstein A., Maintaining shortest paths under deletions in weighted directed graphs, (extended abstract). In: Proceedings of ACM on symposium on theory of computing (STOC), pp. 725-734, (2013)
  • [4] Bouros P., Skiadopoulos S., Dalamagas T., Sacharidis D., Sellis T.K., Evaluating reachability queries over path collections, Proceedings of international conference on scientific and statistical database management (SSDBM), pp. 398-416, (2009)
  • [5] Chang L., Yu J.X., Qin L., Cheng H., Qiao M., The exact distance to destination in undirected world, VLDB J, 21, 6, pp. 869-888, (2012)
  • [6] Cheng J., Ke Y., Chu S., Cheng C., Efficient processing of distance queries in large graphs: a vertex cover approach, Proceedings of international conference on management of data (SIGMOD), pp. 457-468, (2012)
  • [7] Crecelius T., Schenkel R., Pay-as-you-go maintenance of precomputed nearest neighbors in large graphs, Proceedings of ACM conference on information and knowledge management (CIKM), pp. 952-961, (2012)
  • [8] Cuzzocrea A., Papadimitriou A., Katsaros D., Manolopoulos Y., Edge betweenness centrality: a novel algorithm for qos-based topology control over wireless sensor networks, J Netw Comput Appl, 35, 4, pp. 1210-1217, (2012)
  • [9] Demetrescu C., Emiliozzi S., Italiano G.F., Experimental analysis of dynamic all pairs shortest path algorithms, Proceedings of ACM-SIAM symposium on discrete algorithms (SODA, pp. 369-378, (2004)
  • [10] Demetrescu C., Italiano G.F., A new approach to dynamic all pairs shortest paths, J ACM, 51, 6, pp. 968-992, (2004)
12345