Scalable Computation of Acyclic Joins (Extended Abstract)
Summary: Computes acyclic joins of k fully-reduced relations in O(sort(n+z)) I/Os for a broad class of acyclic graphs, eliminating prior Ω((n+z)k) dependence on k and matching reducer+sort cost. Uses subset-size estimates to place tuples (avoids binary decomposition) and gives a 3-cycle bound O(n^2/m+sort(n+z)). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Anna Pagh
- 2. Rasmus Pagh
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 503 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021517145 |
| 1,556 | Beyond Worst-case Analysis for Joins with Minesweeper | 2014 | PODS | 0.00011383141 |
| 2,158 | DIFF: A Relational Interface for Large-Scale Data Explanation | 2019 | VLDB | 9.4117885e-05 |
| 2,963 | Subgraph Matching: on Compression and Computation | 2018 | VLDB | 7.8061004e-05 |
| 4,430 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1879319e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1 | Access Path Selection in a Relational Database Management System | 1979 | SIGMOD | 0.0040465394 |
| 100 | On the Propagation of Errors in the Size of Join Results | 1991 | SIGMOD | 0.00050033475 |
| 811 | Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization | 1991 | SIGMOD | 0.00016385568 |
| 1,065 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014344675 |
| 6,876 | XQuery Optimization | 2003 | VLDB | 4.8947451e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,938 | From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System | 2015 | SIGMOD | 0.00010025547 |
| 8,163 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD | 4.5685178e-05 |
| 4,926 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8184457e-05 |
| 1,621 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD | 0.00011105663 |
| 8,065 | Efficient Computation of Quantiles over Joins | 2023 | PODS | 4.5899218e-05 |
| 8,136 | On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries (Extended Abstract) | 1984 | PODS | 4.5739301e-05 |
| 445 | Computing Joins Of Relations | 1975 | SIGMOD | 0.00023029279 |
| 4,709 | Instance and Output Optimal Parallel Algorithms for Acyclic Joins | 2019 | PODS | 5.9744219e-05 |
| 2,281 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.122455e-05 |
| 4,430 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1879319e-05 |