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
- 2. Aidan Hogan
- 3. Gonzalo Navarro
- 4. Juan L. Reutter
- 5. Javier Rojas-Ledesma
- 6. Adrián Soto
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,481 | MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs | 2024 | SIGMOD | 4.3341665e-05 |
| 9,672 | AvantGraph Query Processing Engine | 2022 | VLDB | 4.3062725e-05 |
| 9,940 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD | 4.2456408e-05 |
| 10,070 | DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs | 2026 | SIGMOD | 4.1945683e-05 |
| 10,199 | R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization | 2026 | SIGMOD | 4.1945683e-05 |
| 10,474 | Community Detection in Heterogeneous Information Networks Without Materialization | 2025 | SIGMOD | 4.1945683e-05 |
| 10,488 | HoneyComb: A Parallel Worst-Case Optimal Join on Multicores | 2025 | SIGMOD | 4.1945683e-05 |
| 11,009 | Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure | 2024 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 342 | EmptyHeaded: A Relational Engine for Graph Processing | 2016 | SIGMOD | 0.00026795977 |
| 502 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021526612 |
| 624 | Hexastore: Sextuple Indexing for Semantic Web Data Management | 2008 | VLDB | 0.00018988711 |
| 1,333 | Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins | 2019 | VLDB | 0.00012523806 |
| 1,442 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00011956109 |
| 2,275 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.1262202e-05 |
| 2,296 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS | 9.0776226e-05 |
| 5,855 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 5.3006096e-05 |
| 8,496 | Dynamic Data Structures for Document Collections and Graphs | 2015 | PODS | 4.4981899e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 900 | Graph Indexing: Tree + Delta >= Graph | 2007 | VLDB | 0.00015495155 |
| 334 | Fast and Practical Indexing and Querying of Very Large Graphs | 2007 | SIGMOD | 0.00027081079 |
| 4,953 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8085795e-05 |
| 6,305 | Free Join: Unifying Worst-Case Optimal and Traditional Joins | 2023 | SIGMOD | 5.1209718e-05 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 4,432 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1938383e-05 |
| 2,296 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS | 9.0776226e-05 |
| 3,515 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0220813e-05 |
| 2,275 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.1262202e-05 |
| 9,940 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD | 4.2456408e-05 |