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: 1792
Venue: PODS
Year: 2019
Pagerank: 6.738679e-05
Overall Rank: 4,371 | 70.02%
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,136	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.7210541e-05
5,463	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.2086169e-05
7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.6915726e-05
8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4608734e-05
8,657	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	5.3907647e-05
9,235	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.3016261e-05
9,478	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.2634238e-05
10,816	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	5.093636e-05
11,132	Topology-aware Parallel Joins	2024	PODS	5.093636e-05
11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	5.093636e-05
11,634	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	5.093636e-05
11,635	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	5.093636e-05
11,677	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	5.093636e-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.00059843817
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
1,699	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.975915e-05
1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.3363505e-05
2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS	9.0066814e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
4,244	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.8062787e-05
4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.7233577e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
2	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
3	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
4	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
5	6,444	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS
6	2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
7	7,386	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
8	5,463	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS
9	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
10	4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS