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 |
|---|---|---|---|---|
| 502 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021526612 |
| 1,557 | Beyond Worst-case Analysis for Joins with Minesweeper | 2014 | PODS | 0.00011392493 |
| 2,154 | DIFF: A Relational Interface for Large-Scale Data Explanation | 2019 | VLDB | 9.4208667e-05 |
| 2,997 | Subgraph Matching: on Compression and Computation | 2018 | VLDB | 7.7559339e-05 |
| 4,432 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1938383e-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.0040449103 |
| 99 | On the Propagation of Errors in the Size of Join Results | 1991 | SIGMOD | 0.00050022914 |
| 813 | Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization | 1991 | SIGMOD | 0.0001639584 |
| 1,064 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014356481 |
| 6,872 | XQuery Optimization | 2003 | VLDB | 4.8991822e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,939 | From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System | 2015 | SIGMOD | 0.00010025655 |
| 8,159 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD | 4.5729025e-05 |
| 4,953 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8085795e-05 |
| 1,619 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD | 0.00011111678 |
| 8,061 | Efficient Computation of Quantiles over Joins | 2023 | PODS | 4.5943269e-05 |
| 8,134 | On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries (Extended Abstract) | 1984 | PODS | 4.5783206e-05 |
| 441 | Computing Joins Of Relations | 1975 | SIGMOD | 0.00023058395 |
| 4,708 | Instance and Output Optimal Parallel Algorithms for Acyclic Joins | 2019 | PODS | 5.980172e-05 |
| 2,275 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB | 9.1262202e-05 |
| 4,432 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS | 6.1938383e-05 |