Output-optimal Parallel Algorithms for Similarity Joins

Summary: Refines Beame et al.'s 2-relation output-optimal parallel join to true optimality and develops output-optimal parallel algorithms for a broad class of similarity joins (ℓ1, ℓ2, ℓ∞), including LSH-based methods. Proves a lower bound ruling out output-optimal algorithms for joins with >2 relations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h332d61ddca1c94d3
Venue: PODS
Year: 2017
Pagerank: 8.4260608e-05
Overall Rank: 2,464 | 83.44%
DOI: 10.1145/3034786.3056110

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{hu_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Output-optimal Parallel Algorithms for Similarity Joins}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056110},
        doi = {10.1145/3034786.3056110},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao and Tao, Yufei and Yi, Ke},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,249	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011340141
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6541797e-05
4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5877664e-05
5,595	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.0727701e-05
5,958	Cheetah: Accelerating Database Queries with Switch Pruning	2020	SIGMOD	5.9338314e-05
6,573	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.7455776e-05
6,704	Distance-Sensitive Hashing	2018	PODS	5.7051402e-05
6,955	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6342744e-05
7,293	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5638766e-05
8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.336718e-05
8,550	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.3168829e-05
9,410	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1826718e-05
9,495	Set Similarity Search for Skewed Data	2018	PODS	5.1708619e-05
11,028	Advances of Query Processing in Vector Databases	2026	VLDB	4.9793485e-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,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	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
12,054	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.9793485e-05
12,194	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
977	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012731794
1,231	Communication Steps for Parallel Query Processing	2013	PODS	0.00011410373
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
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
3,755	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.0452836e-05
4,452	Bounded Conjunctive Queries	2014	VLDB	6.5938977e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,985	Exploiting Database Similarity Joins for Metric Spaces	2012	VLDB
2	8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
3	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
4	7,468	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
5	4,463	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS
6	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
7	360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD
8	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
9	315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
10	12,383	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR