स्ट्रीमिंग फ़्रीक्वेंसी अनुमानों के लिए आप Count-Min Sketch को कैसे लागू करते हैं?

1. प्रश्न

एक लॉगिंग प्लेटफ़ॉर्म को URLs या उत्पाद IDs जैसे ईवेंट कुंजियाँ प्राप्त होती हैं, संभावित रूप से अरबों ईवेंट्स। निश्चित मेमोरी के साथ add(key) और estimate(key) लागू करें। एक अनुमानित घटना गणना (occurrence count) लौटाएं और त्रुटि, शार्ड मर्ज, काउंटर ओवरफ्लो, और एक सटीक संरचना की आवश्यकता कब होती है, इस पर चर्चा करें।

2. बाधाएं और स्पष्टीकरण

• प्रत्येक ईवेंट एक बार देखा जाता है; सभी कुंजियाँ हैश तालिका में फ़िट नहीं हो सकती हैं।
• ओवरएस्टिमेशन स्वीकार्य है, जिसमें पैरामीटर त्रुटि संभावना को नियंत्रित करते हैं।
• गैर-ऋणात्मक (non-negative) अपडेट के साथ प्रारंभ करें; विलोपन (deletion), ऋणात्मक भार, और समय-आधारित समाप्ति (time-based expiry) के लिए अतिरिक्त बाधाओं की आवश्यकता होती है।
• शार्ड्स को सीधे केवल तभी मर्ज किया जा सकता है जब चौड़ाई, गहराई, हैश सीड्स, और काउंटर एन्कोडिंग मेल खाते हों।

3. मुख्य दृष्टिकोण

Count-Min Sketch (CMS) w गैर-ऋणात्मक काउंटरों वाली d पंक्तियाँ बनाए रखता है। प्रत्येक पंक्ति में एक स्वतंत्र हैश फ़ंक्शन होता है जो एक कुंजी को एक कॉलम में मैप करता है। एक अपडेट प्रत्येक चयनित काउंटर को बढ़ाता है; एक क्वेरी न्यूनतम चयनित काउंटर लौटाती है। वास्तविक गणना प्रत्येक चयनित पंक्ति में दिखाई देती है, जबकि अन्य कुंजियों से टकराव (collisions) केवल काउंटरों में जोड़ सकते हैं, इसलिए न्यूनतम एक ऊपरी सीमा (upper bound) है जो कम गिनती (undercount) नहीं करता है।

त्रुटि epsilon और विफलता संभावना delta का उपयोग करते हुए, सामान्य विकल्प w = ceil(e / epsilon) और d = ceil(ln(1 / delta)) हैं। कुल अपडेट भार N के साथ, अनुमान कम से कम 1 - delta की संभावना के साथ अधिकतम वास्तविक गणना प्लस epsilon * N होता है। यह एक संभाव्य त्रुटि सीमा (probabilistic error bound) है, प्रत्येक क्वेरी के लिए एक पूर्ण गारंटी नहीं।

4. संदर्भ कार्यान्वयन

init(epsilon, delta):
  w = ceil(e / epsilon)
  d = ceil(ln(1 / delta))
  table = array(d, w, fill=0)
  seeds = choose_d_independent_seeds()

add(key, weight=1):
  require weight >= 0
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    table[row][col] += weight
  total += weight

estimate(key):
  values = []
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    values.append(table[row][col])
  return min(values)

merge(other):
  require same w, d, seeds, counter encoding
  for each cell (r, c):
    table[r][c] += other.table[r][c]
  total += other.total

5. जटिलता और शुद्धता

प्रत्येक अपडेट और क्वेरी d सेल को छूती है, इसलिए समय O(d) है। स्थान O(d * w) है, जो विशिष्ट कुंजियों की संख्या से स्वतंत्र है। गैर-ऋणात्मक अपडेट के साथ, न्यूनतम कम से कम वास्तविक आवृत्ति बना रहता है। चौड़ाई बढ़ाने से टकराव का पूर्वाग्रह (collision bias) कम होता है; गहराई बढ़ाने से त्रुटि सीमा से अधिक होने की संभावना कम हो जाती है, जबकि दोनों मेमोरी और हैश कार्य को रैखिक रूप से बढ़ाते हैं।

काउंटरों को पर्याप्त पूर्णांक चौड़ाई या एक स्पष्ट संतृप्ति नीति (saturation policy) की आवश्यकता होती है; अहस्ताक्षरित रैपअराउंड (unsigned wraparound) नो-अंडरकाउंट गुण को अमान्य कर देगा। एक शार्ड मर्ज संबंधित सेल को जोड़ता है, और सभी हैश मैपिंग का मेल खाना आवश्यक है। विभिन्न लेआउट्स को संयोजित करने से एक व्याख्या-अयोग्य (uninterpretable) परिणाम उत्पन्न होता है।

6. फॉलो-अप्स और जाल

• CMS किसी ज्ञात कुंजी की अनुमानित गणना का उत्तर देता है; यह Top-K की गणना नहीं करता है। उसके लिए एक उम्मीदवार सेट रखें या एक हेवी-हिटर (heavy-hitter) संरचना का उपयोग करें।
• टकराव केवल ओवरएस्टिमेट करते हैं, इसलिए अनुमान सटीक आवृत्ति या सटीक विशिष्ट सेट को पुनः प्राप्त नहीं कर सकता है।
• ऋणात्मक अपडेट एकरसता (monotonicity) और सरल प्रमाण को तोड़ते हैं; विलोपन और स्लाइडिंग विंडो के लिए आमतौर पर समय बकेट या एक क्षयकारी (decaying) संरचना की आवश्यकता होती है।
• एक समय विंडो को पुराने योगों को घटाकर तब तक बनाए नहीं रखा जा सकता जब तक कि रोलबैक-सक्षम बकेट स्थिति को बनाए न रखा जाए।

7. आगे पढ़ना

CMS की तुलना एक सटीक हैश मैप, Bloom filter, HyperLogLog, और Frequent Items Sketch से करें: वे क्रमशः आवृत्ति प्रश्नों, सदस्यता, कार्डिनैलिटी, और हेवी-हिटर पहचान को लक्षित करते हैं। क्वेरी, त्रुटि बजट, विलोपन आवश्यकताओं, और क्या उम्मीदवार कुंजियों को उत्सर्जित किया जाना चाहिए, इसके आधार पर चयन करें।

8. साक्षात्कार स्कोरिंग बिंदु

काउंटर मैट्रिक्स की व्याख्या कर सकते हैं

उम्मीदवार को स्वतंत्र पंक्ति हैश, प्रत्येक पंक्ति को अपडेट करने, न्यूनतम लेने, और टकराव केवल एक काउंटर को क्यों बढ़ा सकते हैं, इसका वर्णन करना चाहिए।

त्रुटि मापदंडों को बता सकते हैं

उन्हें epsilon, delta, w, d, और कुल भार N को जोड़ना चाहिए, और एक संभाव्यता सीमा को एक पूर्ण सटीक गारंटी से अलग करना चाहिए।

इंजीनियरिंग सीमाओं को संभाल सकते हैं

उन्हें काउंटर ओवरफ्लो, शार्ड-पैरामीटर संगतता, सेल-वार जोड़, और ऋणात्मक भार या स्लाइडिंग विंडो के लिए अतिरिक्त डिज़ाइन को कवर करना चाहिए।

एक उपयुक्त संरचना चुन सकते हैं

उन्हें यह पहचानना चाहिए कि CMS Top-K, सटीक सदस्यता सूचियाँ, या सटीक कार्डिनैलिटी प्रदान नहीं करता है, और आवश्यकताएं बदलने पर एक सटीक मैप, HLL, या हेवी-हिटर संरचना पर स्विच करना चाहिए।