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.5877664e-05
Overall Rank: 4,463 | 70.00%
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,187	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5546613e-05
5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0727701e-05
7,293	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5638766e-05
7,609	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4847975e-05
8,819	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	5.2698104e-05
9,410	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1826718e-05
9,659	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.1453267e-05
11,225	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9793485e-05
11,480	Topology-aware Parallel Joins	2024	PODS	4.9793485e-05
11,493	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS	4.9793485e-05
11,941	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	4.9793485e-05
11,942	Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins	2021	PODS	4.9793485e-05
11,984	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9793485e-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.00059752575
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015341557
977	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012731794
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
1,231	Communication Steps for Parallel Query Processing	2013	PODS	0.00011410373
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020855
1,725	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7902443e-05
2,043	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.1406885e-05
2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS	8.8194236e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6541797e-05
4,475	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.5838041e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,467	Output-sensitive Conjunctive Query Evaluation	2024	PODS
2	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
3	11,027	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,573	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS
6	2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
7	6,805	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
8	5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS
9	3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
10	4,475	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS