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: h36c73a26bf9fb6c4
Venue: PODS
Year: 2019
Pagerank: 6.584648e-05
Overall Rank: 4,466 | 69.99%
DOI: 10.1145/3294052.3319698

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (Hong Kong University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{hu_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Instance and Output Optimal Parallel Algorithms for Acyclic Joins}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319698},
        doi = {10.1145/3294052.3319698},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao and Yi, Ke},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,188	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5510881e-05
5,596	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0698953e-05
7,295	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5612427e-05
7,616	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4822011e-05
8,828	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	5.2673158e-05
9,420	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1802184e-05
9,666	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.142891e-05
11,233	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9769913e-05
11,486	Topology-aware Parallel Joins	2024	PODS	4.9769913e-05
11,499	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9769913e-05
11,947	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9769913e-05
11,948	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9769913e-05
11,990	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9769913e-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
17	Provenance Semirings	2007	PODS	0.00059813669
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019095982
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015334386
978	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012725823
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012068611
1,233	Communication Steps for Parallel Query Processing	2013	PODS	0.00011404978
1,482	Skew in Parallel Query Processing	2014	PODS	0.00010534147
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020376
1,726	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7857214e-05
2,045	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1363731e-05
2,216	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.8152513e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4221003e-05
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6510297e-05
4,477	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.580699e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
2	6,469	Output-sensitive Conjunctive Query Evaluation	2024	PODS
3	11,036	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB
4	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
5	6,576	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS
6	2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
7	6,811	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
8	5,596	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS
9	3,661	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
10	4,477	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS