यह संभव है क्योंकि पेजरैंक eigenvalue का एक रूप था और यही कारण है कि MapReduce पेश किया गया। लेकिन वास्तविक कार्यान्वयन में समस्याएं आती हैं, जैसे हर गुलाम कंप्यूटर को मैट्रिक्स की एक प्रति बनाए रखना है?MapReduce/Hadoop के साथ eigenvalue गणना को कैसे कार्यान्वित करें?
प्रस्तावना:
डेटा का सही ज़ब्ती को देखते हुए, हर मशीन पर एक पूर्ण डाटासेट बिना समानांतर कंप्यूटिंग परिणाम प्राप्त कर सकते हैं। उदाहरण के लिए
लें निम्नलिखित पाश:
for (int i = 0; i < m[].length; i++)
{
for (int j = 0; j < m[i].length; j++)
{
m[i][j]++;
}
}
और निम्नलिखित लेआउट के एक मैट्रिक्स दी:
j=0 j=1 j=2
i=0 [ ] [ ] [ ]
i=1 [ ] [ ] [ ]
i=2 [ ] [ ] [ ]
समानांतर निर्माणों इस तरह मौजूद है कि जम्मू स्तंभ प्रत्येक कंप्यूटर और करने के लिए भेजा जा सकता है एकल कॉलम समानांतर में गणना की जाती है। समांतरता का कठिन हिस्सा तब आता है जब आपके पास लूप होते हैं जिनमें निर्भरताएं होती हैं।
for (int i = 0; i < m[].length; i++)
{
for (int j = 0; j < m[i].length; j++)
{
//For obvious reasons, matrix index verification code removed
m[i][j] = m[i/2][j] + m[i][j+7];
}
}
जाहिर है एक की तरह एक पाश ऊपर अत्यंत समस्याग्रस्त हो जाता है (मैट्रिक्स indexers ध्यान दें।) लेकिन तकनीक छोरों के इन प्रकार unrolling और प्रभावी समानांतर एल्गोरिदम बनाने के लिए मौजूद है।
उत्तर:
ऐसा नहीं है कि गूगल सभी गुलाम कंप्यूटर पर मैट्रिक्स की एक प्रति को बनाए रखने के बिना एक eigenvalue गणना करने के लिए एक समाधान विकसित संभव है। -या- उन्होंने "करीब पर्याप्त" गणना विकसित करने के लिए Monte Carlo या कुछ अन्य Approximation Algorithm जैसे कुछ का उपयोग किया।
असल में, मैं कहूंगा कि Google जितना संभव हो सके उतने लंबे समय तक अपने पेजरैंक एल्गोरिदम के लिए आवश्यक गणना करने के लिए जितना संभव हो सके उतना लंबा होगा। जब आप these और this (ईथरनेट केबल पर ध्यान दें) जैसी मशीनें चला रहे हैं तो आप बड़े डेटासेट (100 गीगा) को स्थानांतरित नहीं कर सकते हैं क्योंकि यह एनआईसी कार्ड की हार्डवेयर सीमाओं को असंभव है।
इसके साथ ही, Google प्रोग्रामर समुदाय को आश्चर्यचकित करने में अच्छा है और उनका कार्यान्वयन पूरी तरह से अलग हो सकता है।
POSTAMBLE:
समानांतर कंप्यूटिंग के लिए कुछ अच्छे संसाधन OpenMP और MPI शामिल होंगे। दोनों समानांतर कार्यान्वयन बहुत अलग मानदंड, जिनमें से कुछ मशीन कार्यान्वयन की वजह से उपजी से समानांतर कंप्यूटिंग दृष्टिकोण (क्लस्टर बनाम वितरित अभिकलन।)
पर एक नज़र डालें "सभी दास कंप्यूटरों पर मैट्रिक्स की एक प्रति बनाए रखने के बिना एक ईजिनवेल की गणना पूरी तरह से संभव है।" ??? आप उस निष्कर्ष पर कैसे आते हैं? पेजरैंक की मैट्रिस स्पैस हैं। –
@ जेसन - मेरा अर्थ और मैंने इसे कैसे लिखा, वही नहीं था। मैंने उस प्रभाव में एक संपादन किया। यह बात बताने के लिए धन्यवाद। –
मुझे लगता है यह उन w/विशेष संरचनाओं को छोड़कर सबसे मैट्रिक्स (जैसे विरल मैट्रिक्स या लोगों के लिए असभ्य है डब्ल्यू/कुछ ब्लॉक पैटर्न)। मैट्रिक्स गुणांक और eigenvalues के बीच बहुत अधिक युग्मन है।
पेजरैंक एक विशेष रूप से बहुत sparse matrix का उपयोग करता है, और इसके eigenvalues की गणना करने से कोई निष्कर्ष लगभग निश्चित रूप से सामान्य matrices तक विस्तार नहीं करता है। (संपादित करें: यहां another reference दिलचस्प लगता है)
अब मैं खुद का उत्तर दे सकता हूं।पेजरैंक एल्गोरिदम स्पैस मैट्रिक्स का लाभ उठाता है जहां इसे कई आत्म-गुणा के साथ eigenvalue में अभिसरण करना चाहिए। इस प्रकार, पेजरैंक अभ्यास में, मानचित्र/घटा प्रक्रिया प्रक्रिया मान्य है। आप मानचित्र प्रक्रिया में मैट्रिक्स गुणा कर सकते हैं और प्रक्रिया को कम करने में एक स्पैर मैट्रिक्स बना सकते हैं। लेकिन सामान्य मैट्रिक्स eigenvalue खोज के लिए, यह अभी भी एक मुश्किल समस्या है।
पेजरैंक नेटवर्क की स्थिर-राज्य पृथक प्रवाह स्थिति को तत्काल रूप से ढूंढकर प्रमुख ईजिनवेक्टर समस्या हल करता है।
NxM मैट्रिक्स नोड एन से लिंक वजन (प्रवाह की मात्रा) का वर्णन करता है, तो मीटर नोड के लिए है, तो सीमा जहां पी एक स्थिर अवस्था (p_n + 1 = p_n) को कन्वर्ज्ड गया है
p_{n+1} = A . p_{n}
, यह eigenvalue के साथ एक eigenvector समस्या है 1.
पेजरैंक एल्गोरिदम को स्मृति में होने वाली मैट्रिक्स की आवश्यकता नहीं है, लेकिन घने (गैर-स्पैस) मैट्रिस पर अक्षम है। घने matrices के लिए, MapReduce गलत समाधान है - आपको नोड्स के बीच इलाके और व्यापक विनिमय की आवश्यकता है - और आपको इसके बजाय लापैक और एमपीआई और दोस्तों को देखना चाहिए।
आप wukong library (रूबी के लिए हडूप स्ट्रीमिंग) में या Heretrix pagerank submodule में एक काम कर रहे पेजरैंक कार्यान्वयन देख सकते हैं। (Heretrix कोड Heretrix की स्वतंत्र रूप से चलता है)
(अस्वीकरण: मैं Wukong के लेखक हूँ।)
अपाचे hama परियोजना जैकोबी eigenvalue एल्गोरिथ्म के कुछ दिलचस्प कार्यान्वयन है। यह हडूप पर चलता है। ध्यान दें कि मानचित्र में मैट्रिक्स के स्कैन में रोटेशन होता है न कि मानचित्र में।
MapReduce के लिए आपको एक विभाजन की आवश्यकता है और एल्गोरिदम जीतें। Http://en.wikipedia.org/wiki/Divide-and-conquer_eigenvalue_algorithm –