Incrementalizing Graph Algorithms

Summary: Incrementalizes batch graph algorithms via a fixpoint model to derive A_delta with cost tied to graph changes and touched region. States correctness and boundedness; uses existing data structures with timestamps; applicable to graph-centric algorithms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6077
Venue: SIGMOD
Year: 2021
Pagerank: 5.5816687e-05
Overall Rank: 5,292 | 63.19%
DOI: 10.1145/3448016.3452796

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,287	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	7.2739447e-05
4,193	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.37019e-05
6,725	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.9484066e-05
9,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
10,311	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1945683e-05
10,489	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.1945683e-05
10,584	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1945683e-05
10,705	Efficient Graph Data Access for Out-of-Memory GPU Streaming Graph Processing	2025	VLDB	4.1945683e-05
10,865	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	4.1945683e-05
10,873	A Single Machine System for Querying Big Graphs with PRAM	2025	VLDB	4.1945683e-05
11,001	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.1945683e-05
11,016	Extending Graph Rules with Oracles	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
278	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00029230623
444	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00022987918
522	Differential dataflow	2013	CIDR	0.00021099241
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
1,720	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010779343
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
4,114	AliCoCo: Alibaba E-commerce Cognitive Concept Net	2020	SIGMOD	6.439922e-05
6,193	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	5.1632545e-05
6,216	Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing	2020	SIGMOD	5.1534945e-05
9,564	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.3254416e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
9,614	Auto-Approximation of Graph Computing	2014	VLDB	4.3177432e-05
1,685	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.0001091808
10,710	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB	4.1945683e-05
5,570	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	5.4284968e-05
2,846	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0234377e-05
6,193	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	5.1632545e-05
9,802	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	4.2807806e-05
1,720	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010779343
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05