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: 5302
Venue: SIGMOD
Year: 2016
Pagerank: 0.00024797217
Overall Rank: 211 | 98.56%
DOI: 10.1145/2882903.2915213

Incoming Non-self Citations Over Time

Authors

1. Christopher R. Aberger (Stanford University)
2. Susan Tu (Stanford University)
3. Christopher Ré (Stanford University)
4. Kunle Olukotun (Stanford University)

BibTeX Citation

@inproceedings{aberger_sigmod16,
        title = {{EmptyHeaded: A Relational Engine for Graph Processing}},
        author = {Aberger, Christopher R. and Tu, Susan and Ré, Christopher and Olukotun, Kunle},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915213},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915213},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 92 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
530	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001709169
809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00013874588
814	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00013841737
1,237	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011545768
1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2787188e-05
2,060	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	9.2454783e-05
2,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1514258e-05
2,126	Kuzu* Graph Database Management System	2023	CIDR	9.1329991e-05
2,182	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	9.010121e-05
2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.9804702e-05
2,769	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1465406e-05
2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	8.0350257e-05
2,915	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	7.9666977e-05
3,027	Sortledton: a Universal, Transactional Graph Data Structure	2022	VLDB	7.8374092e-05
3,102	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	7.7568687e-05
3,194	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.6491858e-05
3,283	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.56675e-05
3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	7.0933895e-05
3,872	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD	7.0580243e-05
3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
4,128	The Relational Data Borg is Learning	2020	VLDB	6.8850804e-05
4,158	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.8628196e-05
4,753	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.5231863e-05
4,892	Fast In-Memory SQL Analytics on Typed Graphs	2017	VLDB	6.4574091e-05
4,983	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.4127092e-05
5,275	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	6.2873652e-05
5,321	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	6.2659937e-05
5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.2472125e-05
5,376	Evolution of a Compiling Query Engine	2021	VLDB	6.2415397e-05
5,461	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.2090515e-05
5,529	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.18591e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
5,781	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	6.0910397e-05
5,870	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	6.061038e-05
5,938	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	6.0343238e-05
6,149	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.9581422e-05
6,159	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.9542729e-05
6,325	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	5.9125893e-05
6,387	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	5.8896555e-05
6,393	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.8879832e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
6,456	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	5.8741786e-05
6,514	A Relational Matrix Algebra and its Implementation in a Column Store	2020	SIGMOD	5.8559163e-05
6,585	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	5.8350362e-05
6,924	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	5.738697e-05
6,961	GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra	2021	VLDB	5.7303405e-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
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
17	Provenance Semirings	2007	PODS	0.00059843817
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
165	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027693424
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
490	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.000175757
759	The case against specialized graph analytics engines	2015	CIDR	0.00014273591
870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.0001350293
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
1,654	Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets	2014	SIGMOD	0.00010104703
2,599	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.3583572e-05
3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.6328776e-05
3,841	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	7.0808098e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,783	Scaling-Up In-Memory Datalog Processing: Observations and Techniques	2019	VLDB
2	631	Relational Joins on Graphics Processors	2008	SIGMOD
3	2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB
4	7,769	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB
5	1,591	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD
6	294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
7	2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD
8	3,872	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD
9	759	The case against specialized graph analytics engines	2015	CIDR
10	7,733	Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded	2017	VLDB