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: 6078
Venue: SIGMOD
Year: 2021
Pagerank: 5.5949839e-05
Overall Rank: 5,266 | 63.41%
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.2689944e-05
4,194	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.3640644e-05
6,729	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.943658e-05
9,486	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3300131e-05
10,323	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1905499e-05
10,499	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.1905499e-05
10,592	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1905499e-05
10,713	Efficient Graph Data Access for Out-of-Memory GPU Streaming Graph Processing	2025	VLDB	4.1905499e-05
10,869	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	4.1905499e-05
10,877	A Single Machine System for Querying Big Graphs with PRAM	2025	VLDB	4.1905499e-05
11,004	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.1905499e-05
11,019	Extending Graph Rules with Oracles	2024	VLDB	4.1905499e-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
271	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00029565193
441	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00023172424
524	Differential dataflow	2013	CIDR	0.00021093133
1,173	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013501079
1,806	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010478244
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
4,109	AliCoCo: Alibaba E-commerce Cognitive Concept Net	2020	SIGMOD	6.4368958e-05
6,195	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	5.1583102e-05
6,209	Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing	2020	SIGMOD	5.1508692e-05
11,711	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
9,614	Auto-Approximation of Graph Computing	2014	VLDB	4.3136057e-05
1,684	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.00010912102
10,717	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB	4.1905499e-05
5,573	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	5.4268881e-05
2,852	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0158741e-05
6,195	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	5.1583102e-05
9,805	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	4.2766788e-05
1,806	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010478244
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05