10.7. COUNTING TRIANGLES
403
But the same tuple E(u, v) must also be treated as a tuple for the term
E(X, Z). We therefore also send the tuple E(u, v) to all Reduce tasks that
correspond to a triple
h(u), y, h(v)

for any y. Finally, we treat E(u, v) as a
tuple of the term E(Y, Z) and send that tuple to all Reduce tasks corresponding
to a triple
x, h(u), h(v)

for any x. The total communication required is thus
3b key-value pairs for each of the m tuples of the edge relation E. That is, the
minimum communication cost is O(mb) if we use b3 Reduce tasks.
Next, let us compute the total execution cost at all the Reduce tasks. As-
sume that the hash function distributes edges suﬃciently randomly that the
Reduce tasks each get approximately the same number of edges. Since the total
number of edges distributed to the b3 Reduce tasks is O(mb), it follows that each
task receives O(m/b2) edges. If we use the algorithm of Section 10.7.2 at each
Reduce task, the total computation at a task is O
(m/b2)3/2
, or O(m3/2/b3).
Since there are b3 Reduce tasks, the total computation cost is O(m3/2), exactly
as for the one-processor algorithm of Section 10.7.2.
10.7.5
Using Fewer Reduce Tasks
By a judicious ordering of the nodes, we can lower the number of reduce tasks
by approximately a factor of 6.
Think of the “name” of the node i as the
pair
h(i), i

, where h is the hash function that we used in Section 10.7.4 to
hash nodes to b buckets.
Order nodes by their name, considering only the
ﬁrst component (i.e., the bucket to which the node hashes), and only using the
second component to break ties among nodes that are in the same bucket.
If we use this ordering of nodes, then the Reduce task corresponding to
list of buckets (i, j, k) will be needed only if i ≤j ≤k. If b is large, then
approximately 1/6 of all b3 sequences of integers, each in the range 1 to b, will
satisfy these inequalities. For any b, the number of such sequences is
b+2
3

(see
Exercise 10.7.4). Thus, the exact ratio is (b + 2)(b + 1)/(6b2).
As there are fewer reducers, we get a substantial decrease in the number
of key-value pairs that must be communicated. Instead of having to send each
of the m edges to 3b Reduce tasks, we need to send each edge to only b tasks.
Speciﬁcally, consider an edge e whose two nodes hash to i and j; these buckets
could be the same or diﬀerent. For each of the b values of k between 1 and b,
consider the list formed from i, j, and k in sorted order. Then the Reduce task
that corresponds to this list requires the edge e. But no other Reduce tasks
require e.
To compare the communication cost of the method of this section with that
of Section 10.7.4, let us ﬁx the number of Reduce tasks, say k. Then the method
of Section 10.7.4 hashes nodes to
3√
k buckets, and therefore communicates
3m
3√
k key-value pairs. On the other hand, the method of this section hashes
nodes to approximately
3√
6k buckets, thus requiring m
3√
6
3√
k communication.
Thus, the ratio of the communication needed by the method of Section 10.7.4
to what is needed here is 3/
3√
6 = 1.65.
Example 10.28 : Consider the straightforward algorithm of Section 10.7.4
