Source-linked AI summary
Sorting, Searching, and Simulation in the MapReduce Framework
Michael T. Goodrich, Nodari Sitchinava, Qin Zhang
TL;DR
The paper asks how MapReduce can be placed on a stronger algorithmic and theoretical foundation for sorting, searching, and parallel computation. It develops efficient MapReduce algorithms and simulations of BSP and CRCW PRAM algorithms, achieving O(logM N) rounds for key applications and constant rounds when M = Θ(N^ε).
Problem
The paper addresses the need for further algorithmic study of MapReduce to approach the theoretical footing of PRAM and BSP, including whether efficient indexed searching is possible.
Method
The paper designs and analyzes MapReduce algorithms for sorting, multi-searching, prefix sums, and simulations of BSP and CRCW PRAM algorithms.
Results
The applications achieve O(logM N) rounds with high probability, while BSP and CRCW PRAM simulations provide stated round and communication bounds; for M = Θ(N^ε), the application algorithms use constant rounds.
Takeaways & Limitations
MapReduce supports efficient multi-searching, truly parallel sorting, and simulations of established parallel models, with applications to convex hulls and fixed-dimensional linear programming.
Takeaways & Limitations
Some supporting results rely on high-probability guarantees, and the authors do not know how to modify their random indexing algorithm to obtain a Las Vegas algorithm.
Abstract
from arXiv · showhide
In this paper, we study the MapReduce framework from an algorithmic standpoint and demonstrate the usefulness of our approach by designing and analyzing efficient MapReduce algorithms for fundamental sorting, searching, and simulation problems. This study is motivated by a goal of ultimately putting the MapReduce framework on an equal theoretical footing with the well-known PRAM and BSP parallel models, which would benefit both the theory and practice of MapReduce algorithms. We describe efficient MapReduce algorithms for sorting, multi-searching, and simulations of parallel algorithms specified in the BSP and CRCW PRAM models. We also provide some applications of these results to problems in parallel computational geometry for the MapReduce framework, which result in efficient MapReduce algorithms for sorting, 2- and 3-dimensional convex hulls, and fixed-dimensional linear programming. For the case when mappers and reducers have a memory/message-I/O size of $M=Θ(N^ε)$, for a small constant $ε>0$, all of our MapReduce algorithms for these applications run in a constant number of rounds.
1 Introduction
The paper develops an algorithmic framework for MapReduce, addressing fundamental sorting, searching, and simulation problems while refining how algorithmic efficiency should be evaluated. Its algorithms support efficient multi-search, truly parallel sorting, and simulations of BSP and CRCW PRAM computations.
- Motivation: The paper studies MapReduce algorithmically through fundamental sorting, searching, and simulation problems, aiming to place it on an equal theoretical footing with PRAM and BSP.
- MapReduce framework: MapReduce computations consist of repeated map-shuffle-reduce rounds, with independent map and reduce operations enabling parallel execution.Map functions process individual values, shuffle groups values by key, and reduce functions process each key-specific list independently.
- Evaluating algorithms: A one-round word-counting algorithm can have R = 1, C = Θ(n), and t = Θ(n), yielding T = Θ(n), no faster than sequential computation.The algorithm maps each word to (w, 1), groups equal words, and sums each group.
- Evaluating algorithms: Evaluating MapReduce algorithms requires considering both round complexity and communication complexity, rather than optimizing the number of rounds alone.A trivial one-round reducer could perform the entire computation sequentially and fail to exploit parallelism.
- Contributions: The paper provides sorting, prefix-sum, and multi-search algorithms in O(logM N) rounds with high probability, becoming constant-round when M = Θ(N^ε).The sorting algorithm is truly parallel because it does not require a central master node to partition data sequentially.
- Contributions: MapReduce supports efficient multi-searching despite having no explicit data or computation locations, countering the claim that it disallows indexed searches.The paper’s multi-search result targets many keys in a roughly equal-sized search tree.
- Contributions: The paper shows efficient simulations of BSP and CRCW PRAM algorithms, including sorting, convex hulls, and fixed-dimensional linear programming.The CRCW PRAM simulation uses an invisible funnel method to route concurrent reads and writes through virtual multi-way trees without explicitly constructing them.
2 Generic MapReduce Computations
The paper defines an abstract graph-and-function model for MapReduce computations and shows how it can express standard MapReduce operations. It develops prefix sums and random indexing with logarithmic round and communication complexity.
- Generic MapReduce Computations: The abstract model represents each node’s state as items and applies a sequential function that emits items to destination nodes over multiple rounds.Communication complexity counts all items sent across rounds, including items sent to oneself; empty nodes contribute nothing.
- Generic MapReduce Computations: The framework captures MapReduce computations with the same round and communication complexities when each node sends, keeps, and receives at most M items per round.The simulation uses Map and Shuffle initially, then Reduce, Map, and Shuffle in later rounds.
- Generic MapReduce Computations: The model designs algorithms by specifying a computation graph G and a sequential function f at each node, rather than directly defining Map and Reduce functions.This representation is described as akin to designing BSP algorithms.
- Prefix Sums and Random Indexing: The all-prefix-sum problem is reformulated for indexed collections of items, computing each item’s prefix value from its associated integer.The tree implementation uses branching factor d = M/2 and height L = ⌈log_d N⌉ = O(log_M N).
- Prefix Sums and Random Indexing: O(log_M N) rounds and O(N log_M N) words of communication suffice for all prefix sums and, with high probability, random indexing.Random indexing applies when input elements carry an estimate of the input size.
3 Simulating BSP and CRCW PRAM Algorithms
The paper simulates BSP and CRCW PRAM algorithms in the I/O-memory-bound MapReduce framework by representing processors, memory, and communication through graph-based computation. The simulations achieve logarithmic overhead for CRCW PRAM and direct applications to sorting and convex hulls.
- Simulation framework: The framework extends prior simulation results by showing how BSP and CRCW PRAM algorithms can be simulated in MapReduce.The CRCW PRAM variant resolves concurrent writes using a commutative semigroup operator such as Sum, Min, or Max.
- Simulating BSP algorithms: A BSP algorithm running for R super-steps with total memory N can be simulated in O(R) MapReduce rounds and O(RN) communication.The reducer memory bound is M = ⌈N/P⌉ for P ≤ N processors.
- Simulating BSP algorithms: The BSP simulation directly yields O(log_M N) rounds and O(N log_M N) communication for sorting and convex hull problems.A randomized sorting algorithm with the same complexity is presented as simpler than directly simulating the BSP sorting algorithm.
- Simulating CRCW PRAM algorithms: The CRCW PRAM simulation routes reads and writes through invisible O(M)-ary trees rooted at memory cells, avoiding explicit Θ(PN) auxiliary memory.The tree height is O(log_M P), which supports bounded reducer memory while aggregating concurrent requests.
- Simulating CRCW PRAM algorithms: Each simulated PRAM step consists of bottom-up reads, top-down reads, internal computation, and bottom-up writes that aggregate conflicts with the semigroup function.Processors receive requested memory items, compute, and issue write requests that are combined toward the corresponding memory-cell root.
- Simulating CRCW PRAM algorithms: O(T log_M P) rounds and O(T(N + P) log_M(N + P)) communication simulate a CRCW PRAM algorithm using T steps, P processors, and N memory cells.Each PRAM round requires O(log_M P) MapReduce rounds, with O(N) items sent per simulated round.
- Simulating CRCW PRAM algorithms: CRCW and CREW PRAM applications, including fixed-dimensional linear programming, achieve O(log_M N) rounds and O(N log_M N) communication.The result follows by directly simulating CRCW PRAM algorithms.
4 Multi-searching and Sorting
The section develops multi-search algorithms for MapReduce, improving communication while preserving logarithmic rounds, and introduces FIFO queuing to simulate modified-framework algorithms safely.
- 4 Multi-searching and Sorting: Multi-search locates each query’s terminating leaf in a balanced search tree and annotates the query accordingly.The input combines a balanced binary search tree T and query set Q.
- 4 Multi-searching and Sorting: The improved algorithm reduces communication by a factor of O(logM N) while retaining O(logM N) round complexity with high probability.The improvement addresses the larger search structure used by the BSP simulation.
- 4 Multi-searching and Sorting: The algorithm partitions queries into O(logM N) random subsets and pipelines their propagation through a shared search DAG.Each subset contains O(N/logM N) queries, and the DAG has O(N) total size.
- 4 Multi-searching and Sorting: O(logM N) rounds and O(N logM N) communication solve multi-search for N queries over a binary search tree with high probability.This is stated as Theorem 4.1.
- 4 Multi-searching and Sorting: FIFO queuing simulates modified-framework algorithms with the same asymptotic round and communication complexities in the original framework.The queue representation uses doubly linked lists and bounded-size blocks.
- 4 Multi-searching and Sorting: The queuing strategy reduces failure probability from N^-Ω(1) to N^-Ω(M), but the authors cannot adapt random indexing to obtain a Las Vegas algorithm.The remaining failure probability is that of the random indexing step.
Appendix A.
The appendix combines brute-force sorting with multi-searching to obtain a sorting algorithm with optimal asymptotic round and communication complexity.
- Appendix A.: Lemma 4.3 sorts N indexed comparable items in O(logM N) rounds with O(N^2 logM N) communication.This is the brute-force sorting bound used as a component.
- Appendix A.: The sorting algorithm selects random pivots, sorts them, and uses the pivots as leaves of a search tree.The pivots receive unique indices before the search tree is built.
- Appendix A.: Multi-search assigns each input item to a bucket, after which all buckets are sorted recursively in parallel.The bucket label is the index associated with the terminating pivot leaf.
- Appendix A.: With high probability, the combined sorting algorithm runs in O(logM N) rounds and O(N logM N) communication.This bound combines Lemma 4.3 with the multi-search algorithm.
A Brute-Force Multi-search and Sorting
The brute-force approach solves multi-search by comparing every query with every search-tree leaf, then derives sorting by using ranks from the same computation.
- A Brute-Force Multi-search and Sorting: Multi-search maps each query to the search-tree leaf where its search path terminates and counts queries terminating at every leaf.The input consists of query items X and sorted leaf items Y.
- A Brute-Force Multi-search and Sorting: The algorithm generates all query–leaf pairs and replicates items across a two-dimensional grid of comparison nodes.Queries and tree items are propagated through logarithmic replication stages.
- A Brute-Force Multi-search and Sorting: Each comparison records whether x_i ≤ y_j, and prefix sums determine the leaf index reached by each query.For each query, the sum of comparison bits gives the terminating leaf position.
- A Brute-Force Multi-search and Sorting: Additional prefix sums count how many query items terminate at each leaf of the search tree.These counts are computed over the comparison results for each leaf.
- A Brute-Force Multi-search and Sorting: Brute-force sorting copies the input as the sorted leaf set, so each computed multi-search index becomes the item’s rank.The rank is obtained from the corresponding k_i value.