हैडोप/मैपराइडस

Question

का उपयोग कर कनेक्टेड घटक ढूंढना मुझे एक विशाल डेटासेट के लिए कनेक्टेड घटकों को खोजने की आवश्यकता है। (ग्राफ को अप्रत्यक्ष किया जा रहा है)

एक स्पष्ट विकल्प MapReduce है। लेकिन मैं MapReduce के लिए नौसिखिया हूं और इसे चुनने और इसे स्वयं कोड करने के लिए समय से कम शांत हूं।

मैं बस सोच रहा था कि इसके लिए कोई मौजूदा एपीआई है क्योंकि यह सोशल नेटवर्क विश्लेषण में एक बहुत ही आम समस्या है?

या कम से कम अगर किसी को किसी भरोसेमंद (कोशिश की और परीक्षण) स्रोत के बारे में पता है, तो कम से कम मैं खुद को कार्यान्वयन के साथ शुरू कर सकता हूं?

धन्यवाद

Answer 1

मैं वास्तव में नहीं जानता कि यदि एक API जो प्रभावशाली तरीके से कनेक्ट घटकों को खोजने के लिए तरीकों है उपलब्ध है। लेकिन, मैंने ग्राफ़ में अन्य नोड्स में स्रोत नोड से दूरी खोजने के लिए बीएफएस एल्गोरिदम लागू किया (ग्राफ 65 मिलियन नोड्स के रूप में बड़ा निर्देशित ग्राफ था)।

विचार एक नवाचार में प्रत्येक नोड के लिए पड़ोसियों (1 की दूरी) का पता लगाने और दूरी को वापस करने तक, मानचित्र को वापस कम करने के आउटपुट को खिलाने का विचार था। नक्शा प्रत्येक नोड से सबसे छोटी दूरी को उत्सर्जित करता है, और सूची से सबसे छोटी दूरी के साथ नोड को अद्यतन करता है।

मैं this out जांचने का सुझाव दूंगा। इसके अलावा, this could help। ये दो लिंक आपको मानचित्र में ग्राफ़ एल्गोरिदम के बारे में मूलभूत विचार देंगे जो प्रतिमान को कम करते हैं (यदि आप पहले से परिचित नहीं हैं)। अनिवार्य रूप से, आपको बीएफएस के बजाय डीएफएस का उपयोग करने के लिए एल्गोरिदम को मोड़ना होगा।

Answer 2

मैं खुद के लिए यह के बारे में ब्लॉग:

http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html

लेकिन MapReduce इन ग्राफ़ विश्लेषण बातों के लिए एक अच्छा फिट नहीं है। उसके लिए बीएसपी (थोक सिंक्रोनस समांतर) का बेहतर उपयोग करें, अपाचे हामा हैडोप एचडीएफएस के शीर्ष पर एक अच्छा ग्राफ एपीआई प्रदान करता है। (Mindist खोज)

https://github.com/thomasjungblut/tjungblut-graph/tree/master/src/de/jungblut/graph/mapreduce

इसके अलावा अपाचे हामा के लिए एक बसपा संस्करण यहां पाया जा सकता:

https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/MindistSearch.java

मैं यहाँ MapReduce के साथ एक जुड़ा घटक एल्गोरिथ्म लिखा है कार्यान्वयन MapReduce में उतना मुश्किल नहीं है और यह कम से कम 10 गुना तेज है। यदि आप रुचि रखते हैं, तो TRUNK में नवीनतम संस्करण देखें और हमारी मेलिंग सूची पर जाएं।

http://hama.apache.org/

http://apache.org/hama/mail-lists.html

Answer 3

आप कार्नेगी मेलॉन विश्वविद्यालय से Pegasus project को देखने के लिए चाहते हो सकता है। वे MapReduce का उपयोग कर एक कुशल और सुरुचिपूर्ण - कार्यान्वयन प्रदान करते हैं। वे द्विआधारी, नमूने और एक बहुत विस्तृत दस्तावेज भी प्रदान करते हैं।

कार्यान्वयन स्वयं 200 9 में यू कंग द्वारा प्रस्तावित सामान्यीकृत इटरेटिव मैट्रिक्स-वेक्टर गुणा (जीआईएम-वी) पर आधारित है।

PEGASUS: A Peta-Scale Graph Mining System - क्रियान्वन और टिप्पणियों यू कांग, Charalampos ई Tsourakakis, क्रिस्टोस फालूसोस डाटा माइनिंग पर आईईईई अंतर्राष्ट्रीय सम्मेलन में (ICDM 2009)

संपादित करें: आधिकारिक कार्यान्वयन वास्तव में के लिए सीमित है 2.1 अरब नोड्स (नोड आईडी पूर्णांक के रूप में संग्रहीत हैं)। मैं अपने पैच और अन्य संवर्द्धन (जैसे स्नैपी संपीड़न) साझा करने के लिए जिथब (https://github.com/placeiq/pegasus) पर एक कांटा बना रहा हूं।

Answer 4

यह एक छोटा सा सवाल है लेकिन यहां कुछ ऐसा है जो आप चेकआउट करना चाहते हैं। हमने स्पार्क मंच पर मानचित्र-कमी का उपयोग करके जुड़े घटक को कार्यान्वित किया।

https://github.com/kwartile/connected-component