Topology-aware Parallel Joins

Summary: Topology-aware parallel join over a directed-graph network; edge costs depend on data moved and link bandwidth, with synchronous rounds and per-round cost = maximum edge cost. An asymptotically optimal binary-join algorithm for symmetric tree topologies, extending topology-aware protocols from set intersection and Cartesian product to skewed inputs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1960
Venue: PODS
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,132 | 23.63%
DOI: 10.1145/3651598

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Xiao Hu (University of Waterloo)
2. Paraschos Koutris (University of Wisconsin)

BibTeX Citation

@inproceedings{hu_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Topology-aware Parallel Joins}},
        url = {https://dl.acm.org/doi/10.1145/3651598},
        doi = {10.1145/3651598},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao and Koutris, Paraschos},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	9.3363505e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.2030591e-05
3,892	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0430255e-05
4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.738679e-05
5,463	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	6.2086169e-05
5,923	Topology Dependent Bounds For FAQs	2019	PODS	6.0411129e-05
7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.6915726e-05
8,394	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.4349805e-05
11,634	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,090	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR
2	7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
3	7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
4	1,974	Track Join: Distributed Joins with Minimal Network Traffic	2014	SIGMOD
5	7,111	Submodularity of Distributed Join Computation	2018	SIGMOD
6	4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS
7	2,892	Scalable and Adaptive Online Joins	2014	VLDB
8	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
9	11,634	Algorithms for a Topology-aware Massively Parallel Computation Model	2021	PODS
10	8,394	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR