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,483 | MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs | 2024 | SIGMOD | 4.3300131e-05 |
| 9,672 | AvantGraph Query Processing Engine | 2022 | VLDB | 4.3021461e-05 |
| 9,940 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD | 4.241573e-05 |
| 10,070 | DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs | 2026 | SIGMOD | 4.1905499e-05 |
| 10,199 | R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization | 2026 | SIGMOD | 4.1905499e-05 |
| 10,484 | Community Detection in Heterogeneous Information Networks Without Materialization | 2025 | SIGMOD | 4.1905499e-05 |
| 10,498 | HoneyComb: A Parallel Worst-Case Optimal Join on Multicores | 2025 | SIGMOD | 4.1905499e-05 |
| 11,012 | Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure | 2024 | VLDB | 4.1905499e-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 |
|---|---|---|---|---|
| 341 | EmptyHeaded: A Relational Engine for Graph Processing | 2016 | SIGMOD | 0.00026850764 |
| 503 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021517145 |
| 625 | Hexastore: Sextuple Indexing for Semantic Web Data Management | 2008 | VLDB | 0.00018963452 |
| 1,334 | Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins | 2019 | VLDB | 0.00012543633 |
| 1,452 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00011922523 |
| 2,281 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.122455e-05 |
| 2,298 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS | 9.0746479e-05 |
| 5,845 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 5.3057391e-05 |
| 8,494 | Dynamic Data Structures for Document Collections and Graphs | 2015 | PODS | 4.493876e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 334 | Fast and Practical Indexing and Querying of Very Large Graphs | 2007 | SIGMOD | 0.00027077424 |
| 895 | Graph Indexing: Tree + Delta >= Graph | 2007 | VLDB | 0.00015498104 |
| 4,926 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8184457e-05 |
| 6,294 | Free Join: Unifying Worst-Case Optimal and Traditional Joins | 2023 | SIGMOD | 5.1202075e-05 |
| 12,302 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1905499e-05 |
| 4,430 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1879319e-05 |
| 2,298 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS | 9.0746479e-05 |
| 3,519 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0181381e-05 |
| 2,281 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.122455e-05 |
| 9,940 | Worst-Case-Optimal Similarity Joins on Graph Databases | 2024 | SIGMOD | 4.241573e-05 |