Finding Connected Components on Map-reduce in Logarithmic Rounds

Details Finding Connected Components on Map-reduce in Logarithmic Rounds Finding Connected Components on Map-reduce in Logarithmic Rounds

2012-03-24

arxiv.org/abs/1203.5387v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Finding Connected Components on Map-reduce in Logarithmic Rounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Connected Components on Map-reduce in Logarithmic Rounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Connected Components on Map-reduce in Logarithmic Rounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-38944