DBScholar

Back to papers

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
h1044757b53a03fd3
Venue
SIGMOD
Year
2016
Pagerank
0.00024899872
Overall Rank
208 | 98.61%
DOI
10.1145/2882903.2915213

Incoming Non-self Citations Over Time

Authors

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 96 citing papers.

Rank Citing Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021236408
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.0001671863
713 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014571507
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013660715
1,180 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011622165
1,252 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011334813
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020376
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
1,753 Kuzu* Graph Database Management System 2023 CIDR 9.7244117e-05
1,853 Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions 2018 SIGMOD 9.499042e-05
1,901 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.4014537e-05
2,017 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1788573e-05
2,070 Traversing Large Graphs on GPUs with Unified Memory 2020 VLDB 9.087777e-05
2,212 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.8195478e-05
2,663 A Layered Aggregate Engine for Analytics Workloads 2019 SIGMOD 8.1542952e-05
2,775 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 8.0288982e-05
2,918 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD 7.8546643e-05
2,961 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 7.8039167e-05
3,012 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7512751e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,165 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5735255e-05
3,801 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 7.0128676e-05
3,881 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9477894e-05
3,994 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8652819e-05
4,077 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8156109e-05
4,124 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7895411e-05
4,161 The Relational Data Borg is Learning 2020 VLDB 6.7669004e-05
4,607 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.501689e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
4,986 Fast In-Memory SQL Analytics on Typed Graphs 2017 VLDB 6.323845e-05
5,013 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3119508e-05
5,383 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.1533182e-05
5,454 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1225019e-05
5,460 Evolution of a Compiling Query Engine 2021 VLDB 6.1210985e-05
5,491 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.1067499e-05
5,602 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.0678238e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
5,904 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9511271e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.9234316e-05
6,047 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.9026722e-05
6,121 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.8779092e-05
6,235 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.8403639e-05
6,268 General and Fractional Hypertree Decompositions: Hard and Easy Cases 2018 PODS 5.8281193e-05
6,487 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 5.7661458e-05
6,506 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.758981e-05
6,517 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.7563618e-05
6,552 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 5.7475822e-05
6,634 A Relational Matrix Algebra and its Implementation in a Column Store 2020 SIGMOD 5.7243855e-05
6,811 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6754603e-05
Previous Page 1 / 2 Next

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.

Previous Page 1 / 1 Next

Semantically Similar Papers