Incremental Graph Computations: Doable and Undoable
ACM Transactions on Database Systems · 30.06.2022 · 47 (2) · 1-44
DOI: 10.1145/3500930 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 23.05.2022. Verfasst von Wenfei Fan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 19-mal zitiert (Crossref) und nennt 75 Literaturangaben. Gefördert von: ERC, Royal Society Wolfson Research Merit Award.
Abstract (Originalsprache)
The incremental problem for a class \( {\mathcal {Q}} \) of graph queries aims to compute, given a query \( Q \in {\mathcal {Q}} \) , graph G , answers Q ( G ) to Q in G and updates ΔG to G as input, changes ΔO to output Q ( G ) such that Q ( G ⊕ ΔG ) = Q ( G )⊕ ΔO . It is called bounded if its cost can be expressed as a polynomial function in the sizes of Q , ΔG and ΔO , which reduces the computations on possibly big G to small ΔG and ΔO . No matter how desirable, however, our first results are negative: For common graph queries such as traversal, connectivity, keyword search, pattern matching, and maximum cardinality matching, their incremental problems are unbounded. In light of the negative results, we propose two characterizations for the effectiveness of incremental graph computation: (a) localizable , if its cost is decided by small neighbors of nodes in ΔG instead of the entire G ; and (b) bounded relative to a batch graph algorithm \( {\mathcal {T}} \) , if the cost is determined by the sizes of ΔG and changes to the affected area that is necessarily checked by any algorithms that incrementalize \( {\mathcal {T}} \) . We show that the incremental computations above are either localizable or relatively bounded by providing corresponding incremental algorithms. That is, we can either reduce the incremental computations on big graphs to small data, or incrementalize existing batch graph algorithms by minimizing unnecessary recomputation. Using real-life and synthetic data, we experimentally verify the effectiveness of our incremental algorithms.
Förderung
- ERC
- Royal Society Wolfson Research Merit Award
Zitieren
APA
Fan, W., & Tian, C. (2022). Incremental Graph Computations: Doable and Undoable. ACM Transactions on Database Systems, 47(2), 1-44. https://doi.org/10.1145/3500930
Vancouver
Fan W, Tian C. Incremental Graph Computations: Doable and Undoable. ACM Transactions on Database Systems. 2022;47(2):1-44. doi:10.1145/3500930
BibTeX
@article{Fan2022,
author = {Fan, Wenfei and Tian, Chao},
title = {Incremental Graph Computations: Doable and Undoable},
journal = {ACM Transactions on Database Systems},
year = {2022},
volume = {47},
number = {2},
pages = {1--44},
doi = {10.1145/3500930}
}
EUVIMED