Med tanke på en stor graf G = (V, E) med miljontals noder och kanter, hur beräknar vi dess anslutna komponenter effektivt? På senare tid har man tagit itu med detta problem i kartläggningen, där det finns en grundläggande kompromiss mellan antalet kartreduceringsrundor och kommunikationen i varje omgång. Att ange d diametern på grafen, och n antalet noder i den största komponenten, alla tidigare tekniker för karta-reducera antingen kräver en linjär,  och d), antal rundor, eller en quadratic, Vi föreslår här två effektiva karta-reduce algoritmer: (i) Hash-Greader-to-Min, som är en randomiserad algoritm baserad på PRAM tekniker, kräver O(log n) rundor och O( skaV  en) kommunikation per runda, och (ii) Hash-to-Min, som är en ny algoritm, bevisligen avslutar i O(log n) iterationer för sökväg grafer. Den bevisteknik som används för Hash-to-Min är ny, men inte tight, och den är faktiskt snabbare än Hash-Greader-to-Min i praktiken. Vi förmodar att det kräver 2 log d rundor och 3 log d rundor och 3  på V +  på E) kommunikation per runda, vilket visas i våra experiment. Med hjälp av sekundär sortering, en standard mapreduce funktion, skalar vi Hash-to-Min till grafer med mycket stora anslutna komponenter. Våra tekniker för anslutna komponenter kan även tillämpas på klusterbildning. Vi föreslår en ny algoritm för agglomerativ enkel länkklustring i kartreducering. Detta är den första kartreduce algoritmen för klustring i högst O(log n) rundor, där n är storleken på den största klustret. Vi visar effektiviteten hos alla våra algoritmer genom detaljerade experiment på stora syntetiska såväl som verkliga datauppsättningar. {1 vibhor.rastogi, 3 laukik, 4 anish.
De tog upp detta senare problem med sin Hash-to-Min algoritm REF, men kan inte bevisa dess prestanda, visar bara att det empiriskt tar 2 log D rundor och O(m + n) kommunikation per runda.
Finding connected components in map-reduce in logarithmic rounds
{'venue': '2013 IEEE 29th International Conference on Data Engineering (ICDE)', 'journal': '2013 IEEE 29th International Conference on Data Engineering (ICDE)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}