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.00024884544
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.00021246
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016726545
712 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014578373
818 Hypertree Decompositions: Questions and Answers 2016 PODS 0.0001366708
1,180 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011627669
1,249 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011340141
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020855
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
1,752 Kuzu* Graph Database Management System 2023 CIDR 9.7289339e-05
1,900 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.4059063e-05
2,014 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1832045e-05
2,019 Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions 2018 SIGMOD 9.1750421e-05
2,068 Traversing Large Graphs on GPUs with Unified Memory 2020 VLDB 9.0920811e-05
2,211 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.8237249e-05
2,663 A Layered Aggregate Engine for Analytics Workloads 2019 SIGMOD 8.1581558e-05
2,774 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 8.0327008e-05
2,916 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD 7.8583302e-05
2,959 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 7.8076128e-05
3,011 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7549462e-05
3,160 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5807496e-05
3,164 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5771124e-05
3,798 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 7.0161889e-05
3,880 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9510799e-05
3,992 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8685334e-05
4,075 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8188389e-05
4,123 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7927568e-05
4,161 The Relational Data Borg is Learning 2020 VLDB 6.7700593e-05
4,605 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.5047683e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
4,950 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3421691e-05
4,984 Fast In-Memory SQL Analytics on Typed Graphs 2017 VLDB 6.3268363e-05
5,010 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3149028e-05
5,377 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.1562325e-05
5,449 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1254016e-05
5,455 Evolution of a Compiling Query Engine 2021 VLDB 6.1239975e-05
5,487 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.1096421e-05
5,601 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.0706976e-05
5,901 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9539374e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.926237e-05
6,045 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.9054678e-05
6,120 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.880693e-05
6,232 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.84313e-05
6,264 General and Fractional Hypertree Decompositions: Hard and Easy Cases 2018 PODS 5.8308708e-05
6,485 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 5.7688767e-05
6,504 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.7617085e-05
6,515 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.7590881e-05
6,550 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 5.7503043e-05
6,631 A Relational Matrix Algebra and its Implementation in a Column Store 2020 SIGMOD 5.7270666e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-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