IncBoost: Scaling Incremental Graph Processing for Edge Deletions and Weight Updates
Open Access
- 20 November 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 915-932
Abstract
Incremental query evaluation is key to efficiently processing rapidly changing graph data. By focusing on the parts of the query results affected by updates, it avoids unnecessary computations, allowing for faster query evaluation. While this technique works well in the cases of edge insertions, its benefit quickly diminishes when the volumes of edge deletions and edge weight updates increases. To address the above scalability issue, this work introduces several techniques for handling large update batches that include many edge deletions and weight updates. First, for edge deletions, this work introduces a bottom-up dependency tracing method to identify the affected vertices. Unlike the existing top-down tracing, it completely avoids traversing the underlying graph, thus more scalable for large deletion batches. Second, for edge weight updates, existing graph systems treat each weight change as an edge deletion (with old weight) followed by an edge insertion (with new weight). This "two-round" method is computationally excessive. This work shows that it is, in fact, possible to handle weight updates directly. Finally, this work shows the benefits of adjusting the processing strategy according to the update volume. We integrated the above ideas into a graph system called IncBoost. Based on our evaluation, IncBoost can scale incremental query evaluation to large update batches that represent 30-60% of the graph size. By contrast, the state-of-the-art streaming graph system (RisGraph) typically fails to yield benefits when the batch size reaches 5-15% of the graph size. Regarding the absolute processing time, IncBoost consistently outperforms RisGraph with 3.1× and 5.2× speedups for edge deletions and weight updates on large batches, respectively.Keywords
Funding Information
- NSF (National Science Foundation) (CCF-2226448, CCF-2106383, CCF-2028714, CCF-2002554, CCF-1813173)
This publication has 37 references indexed in Scilit:
- Estimation of Viterbi path in Bayesian hidden Markov modelsMETRON, 2019
- Incremental Graph Processing for On-line Analytics2019
- Adaptable and Data-Driven Softwarized Networks: Review, Opportunities, and ChallengesProceedings of the IEEE, 2019
- Incremental network design with shortest pathsEuropean Journal of Operational Research, 2014
- Betweenness Centrality – Incremental and Faster2014
- The Web as a Graph: Measurements, Models, and Methods1999
- An Incremental Algorithm for a Generalization of the Shortest-Path ProblemJournal of Algorithms, 1996
- Continuous speech recognition using hidden Markov modelsIEEE ASSP Magazine, 1990
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithmIEEE Transactions on Information Theory, 1967
- Direct solutions of sparse network equations by optimally ordered triangular factorizationProceedings of the IEEE, 1967