Worst-Case Optimal Graph Joins in Almost No Space
Summary: Proposes ring index for worst-case optimal graph joins, encoding triples as cyclic bidirectional strings. A ring replaces six orderings and uses sublinear space beyond the graph; in-memory experiments show faster queries with far less space. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Diego Arroyuelo (Federico Santa María Technical University; Instituto Milenio Fundamentos de Datos)
- 2. Aidan Hogan (Instituto Milenio Fundamentos de Datos; University of Chile)
- 3. Gonzalo Navarro (Instituto Milenio Fundamentos de Datos; University of Chile)
- 4. Juan L. Reutter (Instituto Milenio Fundamentos de Datos; Pontifical Catholic University of Chile)
- 5. Javier Rojas-Ledesma (Instituto Milenio Fundamentos de Datos; University of Chile)
- 6. Adrián Soto (Adolfo Ibáñez University; Instituto Milenio Fundamentos de Datos)
BibTeX Citation
@inproceedings{arroyuelo_sigmod21,
title = {{Worst-Case Optimal Graph Joins in Almost No Space}},
author = {Arroyuelo, Diego and Hogan, Aidan and Navarro, Gonzalo and Reutter, Juan L. and Rojas-Ledesma, Javier and Soto, Adrián},
series = {{SIGMOD} '21},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3448016.3457256},
url = {https://dl.acm.org/doi/10.1145/3448016.3457256},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,502 | MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs | 2024 | SIGMOD | 5.4132367e-05 |
| 9,761 | AvantGraph Query Processing Engine | 2022 | VLDB | 5.2238304e-05 |
| 10,087 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD | 5.1558402e-05 |
| 10,229 | Efficient Meta-subgraph Instance Search over Large Heterogeneous Information Networks | 2026 | SIGMOD | 5.093636e-05 |
| 10,361 | DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs | 2026 | SIGMOD | 5.093636e-05 |
| 10,488 | R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization | 2026 | SIGMOD | 5.093636e-05 |
| 10,754 | Community Detection in Heterogeneous Information Networks Without Materialization | 2025 | SIGMOD | 5.093636e-05 |
| 10,765 | HoneyComb: A Parallel Worst-Case Optimal Join on Multicores | 2025 | SIGMOD | 5.093636e-05 |
| 11,220 | Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure | 2024 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 211 | EmptyHeaded: A Relational Engine for Graph Processing | 2016 | SIGMOD | 0.00024797217 |
| 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS | 0.00021283186 |
| 411 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00018902089 |
| 542 | Hexastore: Sextuple Indexing for Semantic Web Data Management | 2008 | VLDB | 0.00016838296 |
| 809 | Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins | 2019 | VLDB | 0.00013874588 |
| 1,109 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00012142685 |
| 1,740 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.875587e-05 |
| 1,857 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS | 9.6047945e-05 |
| 5,601 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 6.1540123e-05 |
| 8,810 | Dynamic Data Structures for Document Collections and Graphs | 2015 | PODS | 5.3654354e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 727 | Graph Indexing: Tree + Delta >= Graph | 2007 | VLDB |
| 2 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 3 | 5,781 | Free Join: Unifying Worst-Case Optimal and Traditional Joins | 2023 | SIGMOD |
| 4 | 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS |
| 5 | 12,489 | Worst-Case Efficient Range Search Indexing | 2009 | PODS |
| 6 | 4,401 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS |
| 7 | 1,857 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS |
| 8 | 3,617 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS |
| 9 | 1,740 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |
| 10 | 10,087 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD |