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.00024929198
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 97 citing papers.

Rank Citing Paper Year Venue Pagerank
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
536 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016738841
706 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014622696
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013623401
1,171 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011677799
1,253 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011316982
1,568 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010178045
1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010090639
1,764 Kuzu* Graph Database Management System 2023 CIDR 9.6923285e-05
1,860 Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions 2018 SIGMOD 9.4720431e-05
1,907 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.379165e-05
1,988 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.2301018e-05
2,074 Traversing Large Graphs on GPUs with Unified Memory 2020 VLDB 9.06339e-05
2,226 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.7971869e-05
2,594 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 8.2278437e-05
2,673 A Layered Aggregate Engine for Analytics Workloads 2019 SIGMOD 8.1276375e-05
2,930 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD 7.8287763e-05
2,977 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 7.7781129e-05
3,020 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7267183e-05
3,105 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6278115e-05
3,107 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6265309e-05
3,805 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 6.99039e-05
3,885 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9282318e-05
4,011 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.842581e-05
4,099 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.7940875e-05
4,133 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7738028e-05
4,174 The Relational Data Borg is Learning 2020 VLDB 6.750725e-05
4,627 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.4801904e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
4,971 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3209003e-05
5,009 Fast In-Memory SQL Analytics on Typed Graphs 2017 VLDB 6.3030779e-05
5,034 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.2921115e-05
5,404 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.132986e-05
5,469 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1022571e-05
5,475 Evolution of a Compiling Query Engine 2021 VLDB 6.1009218e-05
5,514 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.0866191e-05
5,613 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.048773e-05
5,717 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0067263e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
5,995 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.903845e-05
6,061 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.8831543e-05
6,135 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.8584732e-05
6,245 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.8210521e-05
6,251 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8179719e-05
6,272 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.8112899e-05
6,278 General and Fractional Hypertree Decompositions: Hard and Easy Cases 2018 PODS 5.8092008e-05
6,501 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 5.7470793e-05
6,562 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 5.7287508e-05
6,613 A Relational Matrix Algebra and its Implementation in a Column Store 2020 SIGMOD 5.7168098e-05
6,711 BSX : Subgraph Matching with Batch Backtracking Search 2025 SIGMOD 5.6854796e-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