  Given a large graph G = (V,E) with millions of nodes and edges, how do we
compute its connected components efficiently? Recent work addresses this
problem in map-reduce, where a fundamental trade-off exists between the number
of map-reduce rounds and the communication of each round. Denoting d the
diameter of the graph, and n the number of nodes in the largest component, all
prior map-reduce techniques either require d rounds, or require about n|V| +
|E| communication per round. We propose two randomized map-reduce algorithms --
(i) Hash-Greater-To-Min, which provably requires at most 3log(n) rounds with
high probability, and at most 2(|V| + |E|) communication per round, and (ii)
Hash-to-Min, which has a worse theoretical complexity, but in practice
completes in at most 2log(d) rounds and 3(|V| + |E|) communication per rounds.
  Our techniques for connected components can be applied to clustering as well.
We propose a novel algorithm for agglomerative single linkage clustering in
map-reduce. This is the first algorithm that can provably compute a clustering
in at most O(log(n)) rounds, where n is the size of the largest cluster. We
show the effectiveness of all our algorithms through detailed experiments on
large synthetic as well as real-world datasets.
