Back to Search
Start Over
An efficient SSSP algorithm on time-evolving graphs with prediction of computation results.
- Source :
-
Journal of Parallel & Distributed Computing . Apr2024, Vol. 186, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- Many applications need to execute Single-Source Shortest Paths (SSSP) algorithm on each snapshot of a time-evolving graph, leading to long waiting times experienced by the users of such applications. However, these applications are often time-sensitive, the delayed computation results can lead to the loss of best decision-making opportunities. To address this problem, in this paper we propose an efficient SSSP algorithm for time-evolving graphs, called V-Grouper. The main idea of V-Grouper is to avoid the redundant computations of the same vertex in different snapshots. Our experimental results over real-world time-evolving graphs show that, due to the high similarity of consecutive snapshots, the computation results of one vertex in neighboring snapshots are equal with a high probability. At the beginning of computation, V-Grouper first divides all the versions of a given vertex in different snapshots into vertex groups, where the computation result of each version is predicted based on the aforementioned insight of neighboring snapshots having equal results. The versions of the vertex in each group have the same predicted computation result. During the computation process for each vertex group, only one version needs to participate in computation, avoiding a large number of redundant computations. Experimental results show that V-Grouper is up to 64.31× faster than the state-of-the-art SSSP algorithm. • An efficient algorithm to compute SSSPs of the snapshots of time-evolving graph. • A compact data structure of time-evolving graph to save the memory space and improve the snapshot access speed. • An effective design to speed up the interactions between vertex groups.An effective design to speed up the interactions between vertex groups. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH algorithms
*DATA structures
*FORECASTING
*USER experience
Subjects
Details
- Language :
- English
- ISSN :
- 07437315
- Volume :
- 186
- Database :
- Academic Search Index
- Journal :
- Journal of Parallel & Distributed Computing
- Publication Type :
- Academic Journal
- Accession number :
- 174816142
- Full Text :
- https://doi.org/10.1016/j.jpdc.2023.104830