EmptyHeaded: A Relational Engine for Graph Processing

Summary: EmptyHeaded is a high-level, datalog-like relational graph engine with a novel SIMD-enabled join architecture and data layouts. New optimizer and layouts deliver up to 1,000× speedups vs other high-level systems on graph patterns, PageRank, SSSP, and match Galois on PageRank. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5240
Venue: SIGMOD
Year: 2016
Pagerank: 0.00026795977
Overall Rank: 342 | 97.63%
DOI: 10.1145/2882903.2915213

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 38 of 88 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,934	Fast Local Subgraph Counting	2024	VLDB	4.613363e-05
8,026	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	4.6030518e-05
8,031	BSX : Subgraph Matching with Batch Backtracking Search	2025	SIGMOD	4.6018906e-05
8,034	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	4.6010599e-05
8,267	Revisiting the Design of In-Memory Dynamic Graph Storage	2025	SIGMOD	4.545679e-05
8,396	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD	4.5276541e-05
8,432	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	4.5153924e-05
8,486	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4999394e-05
8,883	Optimizing Parallel Recursive Datalog Evaluation on Multicore Machines	2022	SIGMOD	4.4285471e-05
9,173	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	4.3842827e-05
9,366	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3493859e-05
9,730	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2942813e-05
9,754	Pensieve: Skewness-Aware Version Switching for Efficient Graph Processing	2020	SIGMOD	4.2897489e-05
9,788	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2818172e-05
9,988	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1945683e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1945683e-05
10,014	BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching	2026	SIGMOD	4.1945683e-05
10,084	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	4.1945683e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1945683e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,139	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
10,238	TurboLynx: Schemaless Graph Engine Strikes Back for General-Purpose Analytics	2026	VLDB	4.1945683e-05
10,483	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1945683e-05
10,488	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	4.1945683e-05
10,514	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1945683e-05
10,551	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	4.1945683e-05
10,688	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	4.1945683e-05
10,708	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	4.1945683e-05
10,733	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1945683e-05
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-05
11,132	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.1945683e-05
11,220	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1945683e-05
11,298	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	4.1945683e-05
11,479	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.1945683e-05
11,624	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.1945683e-05
11,783	Graph Data Mining with Arabesque	2017	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.0019005923
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
21	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086087497
31	Provenance Semirings	2007	PODS	0.0007857786
60	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00064439773
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031420034
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026768139
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
613	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019181325
851	The case against specialized graph analytics engines	2015	CIDR	0.0001594441
1,270	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00012926086
1,678	Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets	2014	SIGMOD	0.00010933417
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
2,412	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.8726508e-05
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
5,053	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	5.7323846e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,276	Scaling-Up In-Memory Datalog Processing: Observations and Techniques	2019	VLDB	5.1314426e-05
775	Relational Joins on Graphics Processors	2008	SIGMOD	0.00016823862
7,760	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB	4.6589413e-05
3,036	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6735171e-05
2,130	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD	9.4798556e-05
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
3,988	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD	6.5589605e-05
851	The case against specialized graph analytics engines	2015	CIDR	0.0001594441
7,723	Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded	2017	VLDB	4.6676712e-05