Can map-reduce speed up the count-min-sketch algorithm?

yes. section 3.2 from here.

A key feature of the operations which manipulate the sketch is that they are largely oblivious to the current state of the data structure. That is, the updates to the sketch do not require inspection of the current state. This means that data structure is highly suitable for parallelization and distributed computation. Firstly, each row of the sketch is updated independently of others, so the sketch can be partitioned row-wise among threads on a single machine. But more than this, one can build sketches of different subsets of the data (after agreeing on the same parameters w, d and set of hash functions to use), and these sketches can be combined to give the sketch of the union of the data. Sketch combination is straightforward: given sketch arrays of size w × d, they are combined by summing them up, entry-wise. This implies that sketches can be a useful tool in large scale data analysis, within a distributed model such as MapReduce. Each machine can build and “emit” a sketch of its local data, and these can then be combined at a single machine (i.e. a single reducer simply sums up all the sketches, entry-wise) to generate the sketch of a potentially huge collection of data. This approach can be dramatically more efficient in terms of network communication (and hence time and other resources) than the solution of computing exact counts for each item, and filtering out the low counts.