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: 5241
Venue: SIGMOD
Year: 2016
Pagerank: 0.00026850764
Overall Rank: 341 | 97.64%
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,920	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	4.6120304e-05
7,936	Fast Local Subgraph Counting	2024	VLDB	4.6089395e-05
8,027	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	4.5986382e-05
8,035	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	4.5967078e-05
8,264	Revisiting the Design of In-Memory Dynamic Graph Storage	2025	SIGMOD	4.541321e-05
8,394	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD	4.5233733e-05
8,423	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	4.5112315e-05
8,485	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4956257e-05
8,884	Optimizing Parallel Recursive Datalog Evaluation on Multicore Machines	2022	SIGMOD	4.4243024e-05
9,177	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	4.3800806e-05
9,375	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3452177e-05
9,729	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2901665e-05
9,756	Pensieve: Skewness-Aware Version Switching for Efficient Graph Processing	2020	SIGMOD	4.2856385e-05
9,791	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2777144e-05
9,987	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1905499e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1905499e-05
10,014	BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching	2026	SIGMOD	4.1905499e-05
10,084	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	4.1905499e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1905499e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,139	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1905499e-05
10,238	TurboLynx: Schemaless Graph Engine Strikes Back for General-Purpose Analytics	2026	VLDB	4.1905499e-05
10,493	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1905499e-05
10,498	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	4.1905499e-05
10,523	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1905499e-05
10,560	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	4.1905499e-05
10,696	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	4.1905499e-05
10,715	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	4.1905499e-05
10,740	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1905499e-05
10,951	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1905499e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1905499e-05
11,135	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.1905499e-05
11,222	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1905499e-05
11,300	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB	4.1905499e-05
11,483	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.1905499e-05
11,628	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.1905499e-05
11,791	Graph Data Mining with Arabesque	2017	SIGMOD	4.1905499e-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.0019040811
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
20	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086163998
31	Provenance Semirings	2007	PODS	0.00078516827
59	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.0006445664
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031314629
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
610	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019204048
847	The case against specialized graph analytics engines	2015	CIDR	0.00015939766
1,267	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00012917585
1,679	Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets	2014	SIGMOD	0.00010926732
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
2,409	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.867144e-05
3,449	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0803234e-05
5,050	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	5.7268774e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,276	Scaling-Up In-Memory Datalog Processing: Observations and Techniques	2019	VLDB	5.1265189e-05
771	Relational Joins on Graphics Processors	2008	SIGMOD	0.00016813054
7,759	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB	4.6549638e-05
3,034	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6737281e-05
2,128	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD	9.4804485e-05
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
3,147	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4825501e-05
3,984	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD	6.5587512e-05
847	The case against specialized graph analytics engines	2015	CIDR	0.00015939766
7,721	Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded	2017	VLDB	4.6631706e-05