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.9744219e-05
- Overall Rank
- 4,709 | 67.28%
- 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,785 |
Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries |
2020 |
PODS |
6.7658346e-05 |
| 5,650 |
Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins |
2021 |
PODS |
5.3887172e-05 |
| 7,117 |
Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries |
2020 |
PODS |
4.8205884e-05 |
| 8,163 |
Computing Complex Temporal Join Queries Efficiently |
2022 |
SIGMOD |
4.5685178e-05 |
| 9,335 |
Parallel Query Processing: To Separate Communication from Computation |
2022 |
SIGMOD |
4.351469e-05 |
| 9,640 |
An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs |
2025 |
SIGMOD |
4.3067693e-05 |
| 9,743 |
Output-Sensitive Evaluation of Regular Path Queries |
2025 |
PODS |
4.2856385e-05 |
| 10,553 |
Jodes: Efficient Oblivious Join in the Distributed Setting |
2025 |
VLDB |
4.1905499e-05 |
| 10,915 |
Topology-aware Parallel Joins |
2024 |
PODS |
4.1905499e-05 |
| 10,929 |
Parallel Communication Obliviousness: One Round and Beyond |
2024 |
PODS |
4.1905499e-05 |
| 11,439 |
Algorithms for a Topology-aware Massively Parallel Computation Model |
2021 |
PODS |
4.1905499e-05 |
| 11,440 |
Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins |
2021 |
PODS |
4.1905499e-05 |
| 11,483 |
Vertex-centric Parallel Computation of SQL Queries |
2021 |
SIGMOD |
4.1905499e-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.00078516827 |
| 503 |
Worst-case Optimal Join Algorithms |
2012 |
PODS |
0.00021517145 |
| 770 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.0001686092 |
| 1,114 |
Parallel Evaluation of Conjunctive Queries |
2011 |
PODS |
0.00013871948 |
| 1,411 |
Communication Steps for Parallel Query Processing |
2013 |
PODS |
0.00012118832 |
| 1,452 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011922523 |
| 1,556 |
Beyond Worst-case Analysis for Joins with Minesweeper |
2014 |
PODS |
0.00011383141 |
| 2,173 |
AJAR: Aggregations and Joins over Annotated Relations |
2016 |
PODS |
9.3767985e-05 |
| 2,216 |
Skew in Parallel Query Processing |
2014 |
PODS |
9.2693784e-05 |
| 2,219 |
The Input/Output Complexity of Triangle Enumeration |
2014 |
PODS |
9.2653868e-05 |
| 2,856 |
A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries |
2017 |
PODS |
8.0120856e-05 |
| 3,831 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7146681e-05 |
| 4,430 |
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins |
2016 |
PODS |
6.1879319e-05 |
| 4,641 |
Algorithmic Aspects of Parallel Query Processing |
2018 |
SIGMOD |
6.0215749e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 7,117 |
Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries |
2020 |
PODS |
4.8205884e-05 |
| 2,281 |
Adopting Worst-Case Optimal Joins in Relational Database Systems |
2020 |
VLDB |
9.122455e-05 |
| 8,972 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4150824e-05 |
| 1,938 |
From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System |
2015 |
SIGMOD |
0.00010025547 |
| 8,587 |
Output-Optimal Algorithms for Join-Aggregate Queries |
2025 |
PODS |
4.4853975e-05 |
| 3,831 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7146681e-05 |
| 8,035 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.5967078e-05 |
| 5,650 |
Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins |
2021 |
PODS |
5.3887172e-05 |
| 3,519 |
Scalable Computation of Acyclic Joins (Extended Abstract) |
2006 |
PODS |
7.0181381e-05 |
| 4,430 |
Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins |
2016 |
PODS |
6.1879319e-05 |