Algorithms for a Topology-aware Massively Parallel Computation Model

Summary: Tight lower/upper bounds for set intersection, Cartesian product, and sorting in a topology-aware MPC model that assigns data-dependent costs to edges and measures round cost by the max edge. Focus on tree topologies; algorithms optimal w.r.t. initial data placement, constant-round and simple. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1845
Venue: PODS
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,634 | 20.19%
DOI: 10.1145/3452021.3458318

Incoming Non-self Citations Over Time

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

Authors

1. Xiao Hu (Duke University)
2. Paraschos Koutris (University of Wisconsin)
3. Spyros Blanas (Ohio State University)

BibTeX Citation

@inproceedings{hu_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Algorithms for a Topology-aware Massively Parallel Computation Model}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458318},
        doi = {10.1145/3452021.3458318},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao and Koutris, Paraschos and Blanas, Spyros},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,132	Topology-aware Parallel Joins	2024	PODS	5.093636e-05

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
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
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,389	Parallel Data Analysis Directly on Scientific File Formats	2014	SIGMOD	8.6439053e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
2,539	Minimal MapReduce Algorithms	2013	SIGMOD	8.4526595e-05
3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.2030591e-05
4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.738679e-05
5,923	Topology Dependent Bounds For FAQs	2019	PODS	6.0411129e-05
8,394	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR	5.4349805e-05
9,100	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.3250075e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS
2	6,599	Adaptive Asynchronous Parallelization of Graph Algorithms	2018	SIGMOD
3	11,145	Parallel Communication Obliviousness: One Round and Beyond	2024	PODS
4	3,616	Parallel Local Graph Clustering	2016	VLDB
5	3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
6	1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB
7	4,244	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD
8	11,825	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB
9	11,132	Topology-aware Parallel Joins	2024	PODS
10	8,394	Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale	2020	CIDR