Incremental Graph Computations: Doable and Undoable

Summary: Incremental graph computations: for standard queries such as traversal, connectivity, and pattern matching the incremental problem is unbounded. Introduces localizable and bounded-by-batch notions; gives algorithms that localize updates or reuse batch checks, validated on real graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb940cc8d20084f9c
Venue: SIGMOD
Year: 2017
Pagerank: 7.9419904e-05
Overall Rank: 2,851 | 80.84%
DOI: 10.1145/3055918.3055944

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Chunming Hu (Beihang University)
3. Chao Tian (Beihang University; University of Edinburgh)

BibTeX Citation

@inproceedings{fan_sigmod17,
        title = {{Incremental Graph Computations: Doable and Undoable}},
        author = {Fan, Wenfei and Hu, Chunming and Tian, Chao},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3055918.3055944},
        url = {https://dl.acm.org/doi/10.1145/3055918.3055944},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
947	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00012914714
2,257	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.7434588e-05
2,285	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.6948587e-05
3,687	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0955331e-05
4,540	Incrementalizing Graph Algorithms	2021	SIGMOD	6.5508191e-05
5,513	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0986544e-05
5,554	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.0858703e-05
5,684	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	6.0391416e-05
5,926	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	5.9443878e-05
6,309	Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing	2020	SIGMOD	5.8176815e-05
6,525	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.756805e-05
6,723	Adaptive Asynchronous Parallelization of Graph Algorithms	2018	SIGMOD	5.6951102e-05
6,765	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	5.6872079e-05
6,811	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.6744946e-05
7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.6210836e-05
7,478	Extending Graph Patterns with Conditions	2020	SIGMOD	5.5150923e-05
8,318	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	5.3555659e-05
8,980	Graphsurge: Graph Analytics on View Collections Using Differential Computation	2021	SIGMOD	5.2437006e-05
10,157	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	5.0706053e-05
10,268	Keep Your Distributed Data Warehouse Consistent at a Minimal Cost	2023	SIGMOD	5.0491419e-05
10,479	Maintaining Biconnected Components in Streaming Graphs	2026	SIGMOD	4.9793485e-05
10,636	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.9793485e-05
10,665	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.9793485e-05
11,590	Enriching Relations with Additional Attributes for ER	2024	VLDB	4.9793485e-05
11,978	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9793485e-05
12,210	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039045511
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
293	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021943678
947	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00012914714
1,150	Algorithms for Deferred View Maintenance	1996	SIGMOD	0.00011809311
1,317	Incremental Graph Pattern Matching	2011	SIGMOD	0.00011050011
1,879	Incremental Maintenance for Materialized Views over Semistructured Data	1998	VLDB	9.4424426e-05
3,026	Functional Dependencies for Graphs	2016	SIGMOD	7.7387829e-05
3,066	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6877117e-05
4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.5401646e-05
5,953	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.9359492e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,926	Incrementalization of Graph Partitioning Algorithms	2020	VLDB
2	11,341	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB
3	5,684	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD
4	7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD
5	1,375	Query Preserving Graph Compression	2012	SIGMOD
6	2,285	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD
7	10,157	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB
8	4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD
9	1,317	Incremental Graph Pattern Matching	2011	SIGMOD
10	4,540	Incrementalizing Graph Algorithms	2021	SIGMOD