Upper and Lower Bounds on the Cost of a Map-Reduce Computation

1. INTRODUCTION

• For single-round map-reduce, the paper studies how communication cost and parallelism trade off as work is divided among reducers.It focuses on replication rate and reducer size, the maximum number of inputs assigned to a reducer.Source: §1 · p. 1, §1.1 · p. 1

1.1 Communication and Parallelism for MapReduce

• Replication rate represents mapper communication, while limiting reducer size can enable more parallelism but require redesigning keys and smaller reducers.Execution costs can be combined with the replication-rate function to choose a reducer size for a particular job.Source: §1.1 · p. 1, §1.2 · p. 1

1.2 How the Tradeoff Can Be Used

• The paper frames algorithm selection as choosing reducer size along the replication-rate tradeoff, with computation cost modeled from the reducer’s reduce-function.For a pairwise-comparison reducer, the example models total cost as af(q)+bq; a wall-clock objective may add a cq^2 term.Source: §1.2 · pp. 1–2

1.3 Outline of the Paper

• The paper models a range of problems and studies Hamming distance, triangles and graph patterns, and matrix multiplication, deriving lower bounds and algorithms that match them for various reducer sizes.It reports that two-round matrix-multiplication methods are never worse than one-round methods and can be considerably better.Source: §1.3 · p. 2

1.4 Related Work

• Unlike, this work studies reducer-size and communication tradeoffs for single-round jobs; skew is outside its focus, and high-degree graphs may require alternative algorithms.The model is also described as closely related to data provenance.Source: §1.4 · p. 2

2. THE MODEL

• A problem is represented by finite sets of possible inputs and outputs and a mapping from each output to the inputs on which it depends.Instances contain subsets of the possible inputs; the model assumes an output is not produced unless at least one associated input is present.Source: §2 · p. 2

2.1 Examples of Problems

• Examples include natural joins, triangles, Hamming-distance-1 pairs, and group-by-sum, with outputs associated with their contributing inputs.Group-by-sum differs in that an output may be produced when at least one associated tuple is present.Source: §2.1 · p. 3

2.2 Mapping Schemas

• A mapping schema assigns at most q inputs to each reducer and ensures every output is covered by a reducer holding all of its associated inputs.Replication rate is the average number of reducers to which an input is mapped.Source: §2.2 · p. 3

2.3 Independence of Inputs in the Mappers

• Because mappers assign inputs independently of an instance, replication rate estimates expected communication; when inputs occur independently with probability x, q can be scaled to q1/x for a target of q1 actual inputs.The model’s expected reducer occupancy assumes independent input presence, with significant deviations unlikely for large q.Source: §2.3 · pp. 3–4

2.4 The Recipe for Lower Bounds

• The lower-bound recipe bounds the outputs coverable by q inputs with g(q), counts total inputs and outputs, then uses coverage and monotonicity of g(q)/q to bound replication rate.The method starts from the fact that reducers collectively cover all outputs.Source: §2.4 · p. 4

2.5 Our Results

• Table 1 reports lower bounds using input and output counts and g(q); Table 2 gives representative upper bounds, with detailed alternatives deferred to later sections.Some problems have multiple constructive upper bounds that depend on input parameters.Source: §2.5 · p. 4

3.1 Bounding the Number of Outputs

• A reducer with q inputs can cover at most (q/2) log2 q outputs in the Hamming-distance-1 problem.The proof uses induction on bit-string length.Source: §3.1 · p. 4

3.2 Lower Bound for Hamming Distance 1

• r is at least b / log2 q for Hamming-distance-1 inputs of length b, and the paper gives constructions attaining this bound for multiple reducer sizes.The bound follows from a reducer covering at most (q/2) log2 q outputs.Source: §3.2 · pp. 5–6, §3.3 · p. 6

3.3 Upper Bound for Hamming Distance 1

• For c evenly dividing b, splitting strings into c segments and mapping each to reducers that omit one segment achieves replication rate c and covers every distance-1 pair.Strings differing in one segment share the reducer that omits that segment.Source: §3.3 · p. 6

3.4 An Algorithm for Large q

• With weight-range partitions, strings near the central weights fit reducers with log2 q = b − log2 b plus or minus a constant, and low-border strings are replicated to neighboring reducers.The construction partitions the weights of the left and right halves into ranges; border replication ensures distance-1 pairs share a reducer.Source: §3.4 · pp. 6–7

3.5 Generalization to d Dimensions

• In d dimensions, strings are split into d pieces and low-face border points are replicated, giving replication rate 1 + d/k when k is much smaller than b/d.The construction partitions strings by the weights of their pieces into cells of side k.Source: §3.5 · p. 7

3.6 Larger Hamming Distances

• For distance 2, reducer output capacity can be Ω(q^2) for small q, weakening replication lower bounds; a segment-deletion construction has replication rate approximately (ek/d)^d.The paper says the Hamming-distance-1 analysis does not generalize easily to higher distances.Source: §3.6 · pp. 7–8

4.2 Analysis for Sparse Data Graphs

• For randomly selected sparse edges, the adjusted lower bound matches known algorithms’ replication rate within a constant factor when reducer size counts present edges.The analysis adjusts the target number of possible edges assigned to a reducer so the expected number of present edges is q.Source: §4 · p. 8, §4.2 · p. 8

4.1 Lower and Upper Bound for Finding Triangles

• A reducer receiving q edges can cover at most q^(3/2) triangles, achieved in order of magnitude by assigning all edges among about √(2q) nodes.The passage identifies this as the construction attaining the bound.Source: §4.1 · p. 8
• With all possible edges present, the lower bound is r = Ω(n/√q), matching known algorithms’ upper bound of O(n/√q).The upper bound is stated for the case m = n(n−1)/2.Source: §4.1 · p. 8

4.2 Analysis for Sparse Data Graphs

• For sparse graphs, the target assignment accounts for absent edges, and reducing it by a factor of 2 can make the chance any reducer exceeds q as low as desired for large n and m.The target number of possible edges is calibrated to yield an expected q present edges per reducer.Source: §4.2 · pp. 8–9

5. FINDING INSTANCES OF OTHER GRAPHS

• The analysis extends from triangles to finding instances of any fixed sample graph in a larger data graph.Source: §5 · p. 9
• Examples of sample graphs include cycles of length greater than 3 and complete graphs of a certain size.Source: §5 · p. 9
• The framework also covers searching for instances of other small graphs in the input data graph.Source: §5 · p. 9

5.1 The Alon Class of Sample Graphs

• A graph is in the Alon class when its nodes can be partitioned so each induced subgraph is either a single edge or contains an odd-length Hamiltonian cycle.Source: §5.1 · p. 9
• Every cycle, every graph with a perfect matching, and every complete graph belongs to the Alon class.Source: §5.1 · p. 9
• Odd-length paths are in the Alon class, whereas even-length paths are not.The passage attributes the odd-path decomposition to alternating edges and explains that even paths lack a cycle and leave an odd number of nodes.Source: §5.1 · p. 9

5.2 Lower Bound for the Alon Class

• For an Alon-class sample graph S with s nodes, the number of instances in a graph with m edges is O(m^(s/2)).Source: §5.2 · p. 9
• A reducer with q_i inputs can find O(q_i^(s/2)) instances of S, while a graph with all edges has Ω(n^s) instances.Source: §5.2 · p. 9
• The all-edges instance count need not equal n^s because S may have symmetries, but it is at least n^s/s!.Source: §5.2 · p. 9

• Scaling q by n^2/m accounts for data containing only m of the possible edges.Source: §5.3 · p. 9
• This adjustment yields a lower bound on replication rate for the sparse-graph setting.Source: §5.3 · p. 9
• [2] matches the adjusted lower bound to within a constant factor.Source: §5.3 · p. 9

5.4 Paths of Length Two

• The 2-path problem treats each edge as an unordered pair, so (u, v) can be treated as (v, u) even if that tuple is absent.Source: §5.4 · p. 9

5.4.1 Lower Bound

• For q > 2n, the derived lower bound is less than 1, so it is replaced by the trivial bound r ≥ 1.When q = n^2/2, one reducer can receive all edges and r = 1 is tight.Source: §5.4.1 · p. 9

5.4.2 Upper Bound

• When q = n, assigning one reducer to each node gives replication rate 2, matching the lower bound.Each edge is sent to the reducers for its two endpoints; a reducer combines incident edges to produce paths centered at its node.Source: §5.4.2 · p. 10
• The upper and lower bounds match within a constant factor for small q and large q.The construction uses reducer size q = 2n/k and replication rate r = 2(k − 1), approximately 2k; for large q, both bounds lie between 1 and 2.Source: §5.4.2 · p. 10

5.5 Multiway Join

• The general multiway-join setup treats relation names as edge labels and outputs as sets of s labeled edges satisfying the sample graph.Source: §5.5 · p. 10

5.5.1 A Lower Bound for Multiway Join

• For binary-relation joins, a reducer with q inputs can produce at most q^ρ outputs, where ρ depends on the join hypergraph.For a special case with s = m, the lower bound is r ≥ n^(m−α)q^(1−m/α).Source: §5.5.1 · p. 10
• The lower-bound framework extends to relations of common arity α ≥ 2 and yields a replication-rate bound when ρ = s/α.Source: §5.5.1 · p. 10

5.5.2 Upper Bound for Cases of Multiway Join

• For chain joins, the upper bound matches the lower bound, with the same conclusion for chains with an even number of relations.Source: §5.5.2 · pp. 10–11
• For star joins, the analysis assumes a fact table much larger than the dimension tables and notes that output size depends on dimension-table parameters.Under that setup, the number of outputs can be much smaller than the fact-table size.Source: §5.5.2 · p. 11
• Under the star-join assumptions, the upper-bound result differs from the computed lower bound by a factor treated as constant.Source: §5.5.2 · p. 11
• A fractional edge cover of the query hypergraph provides an upper bound on the query-output size.The paper describes computing a tight output-size bound using the approach in.Source: §5.5.2 · p. 11

6. MATRIX MULTIPLICATION

• Each output t_ik depends on an entire row of R and column of S, or 2n inputs.The paper uses this input-output structure to derive the matrix-multiplication bounds.Source: §6 · p. 11

6.1 The Lower Bound on Replication Rate

• A reducer covering outputs forms a rectangle of rows and columns; its output coverage is maximized by a square, yielding g(q) = q^2/(4n^2).The reducer receives n(w + h) inputs, at most q.Source: §6.1 · p. 12

6.2 Matching Upper Bound on Replication Rate

• The resulting one-phase lower bound is r ≥ 2n^2/q, and the row-and-column grouping algorithm matches it for 2n ≤ q < 2n^2.For q ≥ 2n^2, one reducer can do the job; for q < 2n, no reducer can receive enough input to compute even one output.Source: §6.2 · p. 12

6.3 Matrix Multiplication Using Two Phases

• The two-phase method computes x_ijk products and partial sums in phase one, then sums partial sums by (i, k) to produce t_ik in phase two.The second phase is embarrassingly parallel, but communication from both phases must be counted.Source: §6.3 · p. 12
• For each j, a first-phase reducer covers a rectangle of row and column indices; with s rows, s columns, and t j-values, first-phase communication is 2n^3/s.The number of reducers is (n/s)^2(n/t), and each input element is sent to n/s reducers.Source: §6.3 · p. 13
• With first-phase reducer size 2st = q, minimum communication occurs at s = 2t, so the two-phase tiles have 2:1 rectangular aspect ratio.The resulting parameters are t = √q/2 and s = √q.Source: §6.3 · pp. 12–13
• Except when one reducer handles the job, the two-phase method uses less communication than the optimum one-phase method, often much less for small q.Both methods perform the same arithmetic operations the same number of times.Source: §6.3 · p. 13

7. SUMMARY

• Replication rate and reducer input size represent communication cost and compute-node capabilities, and the paper establishes precise tradeoff formulas for several problem families.The analyzed problems include Hamming-distance search, graph patterns, multiway joins, and matrix multiplication.Source: §7 · pp. 13–14

7.1 Open Problems

• Further work is needed on other problems, including Hamming distances greater than 1 and similarity joins beyond Hamming distance.The paper also leaves open how closely its general multiway-join lower bound matches the upper bounds in, noting neither has a closed formula.Source: §7.1 · p. 14
• The paper proposes exploring analyses of algorithms with two or more map-reduce rounds, including SQL joins followed by aggregations.Source: §7.1 · p. 14