Google Trends का सिस्टम डिज़ाइन?

Question

मैं Google Trends (या ट्विटर जैसी किसी भी अन्य बड़े पैमाने पर प्रवृत्ति सुविधा) के पीछे सिस्टम डिज़ाइन को समझने की कोशिश कर रहा हूं।

चुनौतियां:

• डेटा की बड़ी राशि प्रवृत्ति गणना करने के लिए कार्रवाई करने के लिए की आवश्यकता।

• छनन समर्थन - समय, क्षेत्र, वर्ग आदि

• द्वारा एक तरह से संग्रह/ऑफ़लाइन प्रसंस्करण के लिए स्टोर करने के लिए की आवश्यकता है। फ़िल्टरिंग समर्थन के लिए बहु आयाम भंडारण की आवश्यकता हो सकती है।

यह वही मेरी धारणा है

उपयोगकर्ता से प्रत्येक खोज आइटम विशेषताओं है कि संग्रहीत किया जाएगा और अंत में संसाधित का सेट बनाए रखेंगे (मैं MapReduce/NoSQL प्रौद्योगिकियों के शून्य व्यावहारिक अनुभव है)।

साथ ही समय स्टाम्प, खोज के क्षेत्र, वर्ग आदि द्वारा खोजों की सूची बनाए रखने

उदाहरण:

Kurt-> (Time stamp, Region of search origin, category ,etc.) 

Cobain-> (Time stamp, Region of search origin, category ,etc.) 

प्रश्न::

Kurt Cobain अवधि के लिए खोज

• वे खोज शब्द की आवृत्ति की कुशलतापूर्वक गणना कैसे करते हैं?

• दूसरे शब्दों में, एक बड़ा डेटा सेट दिया गया, वे वितरित पैमाने पर सक्षम तरीके से शीर्ष 10 लगातार आइटम कैसे ढूंढते हैं?

Answer 1

खैर आरंभ करने के लिए उपलब्ध हैं ... शीर्ष के शब्दों को खोजने में वास्तव में एक बड़ी समस्या नहीं है। इस क्षेत्र में प्रमुख विचारों में से एक "धारा प्रसंस्करण" का विचार रहा है, यानी डेटा के एक ही पास में ऑपरेशन करने और संभाव्य उत्तर प्राप्त करने के लिए कुछ सटीकता बलिदान करने का विचार किया गया है।इस प्रकार, आप निम्नलिखित की तरह डेटा की एक धारा प्राप्त मान:

एक बी कश्मीर ए सी ए बी बी सी डी एफ जी ए बी एफ एच मैं बी ए सी एफ मैं यू एक्स ए सी

क्या आप चाहते हैं शीर्ष कश्मीर आइटम है। नैतिक रूप से, प्रत्येक आइटम के लिए काउंटर बनाए रखेगा, और अंत में प्रत्येक आइटम की गिनती के अनुसार। यह O(U) स्थान और O(max(U*log(U), N)) समय लेता है, जहां U अद्वितीय आइटमों की संख्या और N है सूची में आइटमों की संख्या।

U छोटा है, यह वास्तव में एक बड़ी समस्या नहीं है। लेकिन एक बार जब आप अनन्य खोजों के अरबों या ट्रिलियन के साथ खोज लॉग के डोमेन में हैं, तो अंतरिक्ष खपत एक समस्या बनने लगती है।

तो, लोग "गिनती-स्केच" के विचार के साथ आए (आप यहां और अधिक पढ़ सकते हैं: count min sketch page on wikipedia)। यहाँ आप लंबाई n के हैश तालिका एक को बनाए रखने और प्रत्येक आइटम के लिए दो हैश बनाने के लिए: संभावना 0.5

फिर आप A[h1[x]] += h2[x] कर के साथ एक समान संभावना

h2(x) = 0/1 प्रत्येक के साथ

h1(x) = 0 ... n-1। मुख्य अवलोकन यह है कि चूंकि प्रत्येक मान यादृच्छिक रूप से +/- 1, E[ A[h1[x]] * h2[x] ] = count(x) है, जहां E अभिव्यक्ति का अपेक्षित मान है, और गणना धारा में एक्स दिखाई देने की संख्या है।

बेशक, इस दृष्टिकोण के साथ समस्या यह है कि प्रत्येक अनुमान में अभी भी एक बड़ा अंतर है, लेकिन इसे हैश काउंटरों का एक बड़ा सेट बनाए रखने और प्रत्येक सेट से औसत या न्यूनतम गणना प्राप्त करके निपटाया जा सकता है।

इस स्केच डेटा संरचना के साथ, आप प्रत्येक आइटम की अनुमानित आवृत्ति प्राप्त करने में सक्षम हैं। अब, आप अभी तक सबसे बड़ी आवृत्ति अनुमानों के साथ 10 आइटमों की एक सूची बनाए रखते हैं, और अंत में आपकी सूची होगी।

Answer 2

वास्तव में किस प्रकार एक विशेष निजी कंपनी यह नहीं होने की संभावना सार्वजनिक रूप से उपलब्ध है, और कैसे एक ऐसी प्रणाली के प्रभाव का मूल्यांकन करने के लिए है है करता है डिजाइनर के विवेक (यह आप या गूगल या जो कोई भी हो) पर

लेकिन शुरू करने के लिए कई टूल और शोध वहां मौजूद हैं। Storm जैसे शीर्ष-स्तरीय अपाचे प्रोजेक्ट्स सहित कई बिग डेटा टूल्स देखें, जो रीयल-टाइम

में स्ट्रीमिंग डेटा की प्रसंस्करण की अनुमति देता है, कुछ बड़े डेटा और वेब साइंस सम्मेलन भी देखें KDD या WSDM, साथ ही कागजात की तरह Google शोध

द्वारा

बाहर कैसे डिजाइन करने के लिए एक ऐसी प्रणाली कोई सही जवाब के साथ चुनौती दे रहा है, लेकिन उपकरण और अनुसंधान आप