Back to papers
Instance and Output Optimal Parallel Algorithms for Acyclic Joins
Summary: Instance-optimal MPC algorithms for r-hierarchical acyclic joins; a new MPC algorithm for arbitrary acyclic joins with load O(IN/p + sqrt(IN·OUT)/p), improving the MPC Yannakakis bound. Proves output-optimality when OUT=O(p·IN) for non-r-hierarchical joins and gives the first output-sensitive MPC lower bound for the triangle, showing triangles are inherently harder.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1760
- Venue
- PODS
- Year
- 2019
- Pagerank
- 5.980172e-05
- Overall Rank
- 4,708 | 67.25%
- DOI
-
10.1145/3294052.3319698
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 13 of 13 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 3,781 |
Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries |
2020 |
PODS |
6.7723513e-05 |
| 5,639 |
Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins |
2021 |
PODS |
5.393897e-05 |
| 7,122 |
Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries |
2020 |
PODS |
4.8252188e-05 |
| 8,159 |
Computing Complex Temporal Join Queries Efficiently |
2022 |
SIGMOD |
4.5729025e-05 |
| 9,330 |
Parallel Query Processing: To Separate Communication from Computation |
2022 |
SIGMOD |
4.3556432e-05 |
| 9,641 |
An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs |
2025 |
SIGMOD |
4.3109001e-05 |
| 9,744 |
Output-Sensitive Evaluation of Regular Path Queries |
2025 |
PODS |
4.2897489e-05 |
| 10,544 |
Jodes: Efficient Oblivious Join in the Distributed Setting |
2025 |
VLDB |
4.1945683e-05 |
| 10,911 |
Topology-aware Parallel Joins |
2024 |
PODS |
4.1945683e-05 |
| 10,925 |
Parallel Communication Obliviousness: One Round and Beyond |
2024 |
PODS |
4.1945683e-05 |
| 11,436 |
Algorithms for a Topology-aware Massively Parallel Computation Model |
2021 |
PODS |
4.1945683e-05 |
| 11,437 |
Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins |
2021 |
PODS |
4.1945683e-05 |
| 11,479 |
Vertex-centric Parallel Computation of SQL Queries |
2021 |
SIGMOD |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 14 of 14 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.0007857786 |
| 502 |
Worst-case Optimal Join Algorithms |
2012 |
PODS |
0.00021526612 |
| 772 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.00016876498 |
| 1,110 |
Parallel Evaluation of Conjunctive Queries |
2011 |
PODS |
0.00013968198 |
| 1,411 |
Communication Steps for Parallel Query Processing |
2013 |
PODS |
0.0001212565 |
| 1,442 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011956109 |
| 1,557 |
Beyond Worst-case Analysis for Joins with Minesweeper |
2014 |
PODS |
0.00011392493 |
| 2,169 |
AJAR: Aggregations and Joins over Annotated Relations |
2016 |
PODS |
9.3845975e-05 |
| 2,212 |
Skew in Parallel Query Processing |
2014 |
PODS |
9.2771827e-05 |
| 2,215 |
The Input/Output Complexity of Triangle Enumeration |
2014 |
PODS |
9.2717602e-05 |
| 2,849 |
A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries |
2017 |
PODS |
8.0195487e-05 |
| 3,833 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7173578e-05 |
| 4,432 |
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins |
2016 |
PODS |
6.1938383e-05 |
| 4,689 |
Algorithmic Aspects of Parallel Query Processing |
2018 |
SIGMOD |
5.9980099e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 7,122 |
Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries |
2020 |
PODS |
4.8252188e-05 |
| 2,275 |
Adopting Worst-Case Optimal Joins in Relational Database Systems |
2020 |
VLDB |
9.1262202e-05 |
| 8,966 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4193184e-05 |
| 1,939 |
From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System |
2015 |
SIGMOD |
0.00010025655 |
| 8,589 |
Output-Optimal Algorithms for Join-Aggregate Queries |
2025 |
PODS |
4.4897014e-05 |
| 3,833 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7173578e-05 |
| 8,034 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.6010599e-05 |
| 5,639 |
Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins |
2021 |
PODS |
5.393897e-05 |
| 3,515 |
Scalable Computation of Acyclic Joins (Extended Abstract) |
2006 |
PODS |
7.0220813e-05 |
| 4,432 |
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins |
2016 |
PODS |
6.1938383e-05 |