Cache-Efficient Fork-Processing Patterns on Large Graphs

Summary: FPP on large graphs suffers cache misses on multi-core systems. ForkGraph partitions graphs into LLC-sized blocks, buffers FPP queries per partition, and uses cache-resident sequential processing with intra- and inter-partition scheduling (yielding and priority-based), achieving work-efficiency and large speedups over Ligra, Gemini, GraphIt. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6145
Venue: SIGMOD
Year: 2021
Pagerank: 5.2471834e-05
Overall Rank: 5,966 | 58.54%
DOI: 10.1145/3448016.3457253

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,420	CoroGraph: Bridging Cache Efficiency and Work Efficiency for Graph Algorithm Execution	2024	VLDB	7.1120128e-05
6,063	ThunderRW: An In-Memory Graph Random Walk Engine	2021	VLDB	5.2259989e-05
9,367	MITra: A Framework for Multi-Instance Graph Traversal	2023	VLDB	4.3466395e-05
9,604	GeaFlow: A Graph Extended and Accelerated Dataflow System	2023	SIGMOD	4.3136057e-05
9,796	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	4.2777144e-05
10,044	ACGraph: An Efficient Asynchronous Out-of-Core Graph Processing Framework	2026	SIGMOD	4.1905499e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1905499e-05
11,000	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
136	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00042409816
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
336	Data-Oriented Transaction Execution	2010	VLDB	0.00027008897
515	QPipe: A Simultaneously Pipelined Relational Query Engine	2005	SIGMOD	0.00021209491
1,046	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00014446882
1,138	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	0.00013715114
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013404419
1,369	Aether: A Scalable Approach to Logging	2010	VLDB	0.0001235533
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010958779
1,670	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010944596
3,235	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	7.3298263e-05
3,600	Parallel Local Graph Clustering	2016	VLDB	6.9285467e-05
3,760	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	6.7790524e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,650	Locality-Aware Cache Replacement Policy for Graph Traversals	2025	VLDB	4.1905499e-05
1,670	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010944596
3,420	CoroGraph: Bridging Cache Efficiency and Work Efficiency for Graph Algorithm Execution	2024	VLDB	7.1120128e-05
9,070	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB	4.3982218e-05
3,600	Parallel Local Graph Clustering	2016	VLDB	6.9285467e-05
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
5,811	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	5.3168243e-05
4,845	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD	5.8731048e-05
570	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019895021
1,684	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.00010912102