Incrementalizing Graph Algorithms

CategoryPublications Publications 326

Authors: Wenfei Fan, ChaoTian, Ruiqi Xu, Qiang Yin, Wenyuan Yu, Jingren Zhou

Name of Conference: ACM Conference on Management of Data (SIGMOD 2021),June 20-25,2021, Xi’an, Shaanxi, China

Date of Publication: June, 2021


Incremental algorithms are important to dynamic graph analyses, but are hard to write and analyze. Few incremental graph algorithms are in place, and even fewer offer performance guarantees.

This paper approaches this by proposing to incrementalize existing batch algorithms. We identify a class of incrementalizable algorithms abstracted in a fixpoint model. We show how to deduce an incremental algorithm AΔ from such an algorithm A. Moreover, AΔ can be made bounded relative to A, i.e., its cost is determined by the sizes of changes to graphs and changes to the affected area that is necessarily checked by batch algorithm A. We provide generic conditions under which a deduced algorithm AΔ warrants to be correct and relatively bounded, by adopting the same logic and data structures of A, at most using timestamps as an additional auxiliary structure. Based on these, we show that a variety of graph-centric algorithms can be incrementalized with relative boundedness. Using real-life and synthetic graphs, we experimentally verify the scalability and efficiency of the incrementalized algorithms.

View Full Text

Keywords2021SIGMODWenfei Fan Previous: Next: