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 10 of 10 citing papers.
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 |
|---|---|---|---|---|
| 208 | EmptyHeaded: A Relational Engine for Graph Processing | 2016 | SIGMOD | 0.00024884544 |
| 315 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS | 0.00021246 |
| 402 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00019104625 |
| 557 | Hexastore: Sextuple Indexing for Semantic Web Data Management | 2008 | VLDB | 0.00016497067 |
| 712 | Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins | 2019 | VLDB | 0.00014578373 |
| 1,091 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00012074152 |
| 1,596 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 0.00010127607 |
| 1,812 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS | 9.5803973e-05 |
| 4,752 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 6.434561e-05 |
| 8,959 | Dynamic Data Structures for Document Collections and Graphs | 2015 | PODS | 5.2503805e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,494 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 2 | 5,010 | Free Join: Unifying Worst-Case Optimal and Traditional Joins | 2023 | SIGMOD |
| 3 | 315 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS |
| 4 | 12,779 | Worst-Case Efficient Range Search Indexing | 2009 | PODS |
| 5 | 4,475 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS |
| 6 | 1,812 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS |
| 7 | 10,854 | Worst-Case Optimal BGPs on Temporal Graphs | 2026 | VLDB |
| 8 | 3,660 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS |
| 9 | 1,596 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |
| 10 | 10,301 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD |