HyperLogLog: भिन्न मानों की संख्या का बहुत सटीक अनुमान कैसे लगाएँ
बहुसमुच्चय में भिन्न मानों की संख्या का अनुमान लगाने वाले एल्गोरिद्मों की शृंखला state of the art एल्गोरिद्म HyperLogLog के लेख के साथ आगे बढ़ती है। फिर भी इस एल्गोरिद्म के पीछे के सभी विचार पहले बताए गए LogLog से आते हैं, इसलिए यदि आप आगे पढ़ना चाहते हैं, तो पक्का कर लीजिए कि आप LogLog को अच्छी तरह जानते हैं।
LogLog एल्गोरिद्म की दो मुख्य समस्याएँ थीं:
बाह्य मान (outliers)
LogLog का परिणामी अनुमान बाह्य मानों (outliers), यानी ऐसे मानों, जो बाकी मानों से बहुत दूर हैं, के प्रति बहुत संवेदनशील है। प्रायः ऐसा होता है कि प्रत्येक समूह के लिए शून्यों वाले प्रत्यय की अधिकतम लंबाइयाँ लगभग समान होती हैं, उदाहरण के लिए 12 और 15 के बीच, पर फिर धड़ाम — और एक शून्यों वाले प्रत्यय की लंबाई 27 है। यह बड़ा अंतर अद्वितीय मानों की संख्या के परिणामी अनुमान को बिगाड़ देता है, क्योंकि सामान्य समांतर माध्य इसे ठीक से नहीं सँभाल पाता। असल में यहाँ वही सिद्धांत काम करता है, जैसे कुछ शीर्ष प्रबंधक और निदेशक अपने ऊँचे वेतन से देश के औसत वेतन को ऊपर खींच लेते हैं।
एल्गोरिद्म के लेखकों ने इसे सुलझाने के लिए बाह्य मानों को हटाने का प्रयास किया और माध्य में कुछ सबसे बड़े अधिकतम मान नहीं गिने, परंतु यह बहुत अच्छा हल नहीं था। बाद में उन्होंने दूसरी विधि आज़माई — समांतर माध्य के बजाय हरात्मक माध्य का प्रयोग किया, जिसके गुण माध्य से दूर स्थित मानों की स्थिति में कहीं बेहतर होते हैं।
छोटी गणनसंख्या के लिए बहुत खराब परिणाम
छोटे बहुसमुच्चयों की गणनसंख्या का अनुमान लगाने में LogLog के परिणाम भयानक होते हैं। यदि बहुसमुच्चय में कुछ ही अद्वितीय अवयव हों, तो LogLog हमें बेतुका बड़ा अनुमान लौटाता है। लेखकों ने इसे चतुराई से सुलझाया — जब इनपुट पर कम गणनसंख्या वाला बहुसमुच्चय हो, तो LogLog एल्गोरिद्म का नहीं, बल्कि बिल्कुल दूसरे एल्गोरिद्म का प्रयोग होता है, यानी पुराने परिचित Linear counting का। ठीक है, पर हम कैसे पहचानें कि इनपुट पर कम गणनसंख्या वाला बहुसमुच्चय है, जब गणनसंख्या ही हमें पता नहीं?
हम LogLog से अद्वितीय अवयवों की संख्या का अनुमान लगवाते हैं और यदि पता चले कि यह अनुमान अपेक्षाकृत कम है, तो अनुमान को छोड़कर Linear counting एल्गोरिद्म से उसे दोबारा परिकलित करते हैं। संक्षेप में याद कर लें कि Linear counting कैसे काम करता है। शुरुआत में हम किसी पूर्वनिर्धारित आकार की, सामान्यतः दो की घात जितनी, शून्यों वाली (बिट) सरणी आवंटित करते हैं। हम बहुसमुच्चय के सभी अवयवों से गुज़रते हैं, उनका हैश परिकलित करते हैं और उसे 0 से लेकर सरणी की लंबाई घटा 1 तक के अंतराल के पूर्णांक i में बदलते हैं। फिर सरणी में सूचकांक i पर 1 सहेजते हैं। अंत में सरणी में शून्यों और इकाइयों की संख्या गिनते हैं और सरल सूत्र से गणनसंख्या का अनुमान लगाते हैं।
परंतु LogLog एल्गोरिद्म ऐसी कोई बिट सरणी प्रयोग नहीं करता, जिसमें वह परिकलित हैश “सहेजे”। इसके बजाय वह ऐसी सरणी प्रयोग करता है, जिसमें प्रत्ययों की अधिकतम लंबाइयाँ रखी जाती हैं। सरणी, उदाहरण के लिए, ऐसी दिख सकती है:
[2, 5, 9, 0, 5, 4, 4, 0]
जहाँ प्रत्येक संख्या परिकलित हैश मानों के दिए गए समूह में शून्यों वाले प्रत्यय की अधिकतम लंबाई बताती है। तब i-वें स्थान पर अशून्य मान का अनिवार्य रूप से अर्थ है कि बहुसमुच्चय के मानों में कोई ऐसा अवयव है, जिसका (तीन-बिट) हैश i के बराबर है। दूसरे शब्दों में, इस सरणी को हम linear counting के लिए बिट सरणी में इस तरह बदल सकते हैं कि शून्य वैसे ही रहें और प्रत्येक धनात्मक संख्या 1 बन जाए। पिछली सरणी से हमें यह बिट सरणी मिलेगी:
[1, 1, 1, 0, 1, 1, 1, 0]
अब हम Linear counting एल्गोरिद्म लागू कर सकते हैं और उसकी सहायता से गणनसंख्या का अनुमान लगा सकते हैं।
परंतु इसमें एक पेच है। सरणी में हम शून्यों वाला अधिकतम प्रत्यय सहेजते हैं, पर क्या हो, यदि किसी समूह में सभी हैश 1 पर समाप्त हों? उदाहरण के लिए, यदि हम अंतिम तीन बिटों को उस समूह के पहचानकर्ता के रूप में लें, जिसमें हैश आता है, तो इस हैश “01001100” के शून्यों वाले प्रत्यय की लंबाई शून्य होगी — क्योंकि सदिश “01001” 1 पर समाप्त होता है। तब अधिकतम मानों की सरणी में सूचकांक 4 (1002=410) पर हम शून्य सहेजते। परंतु linear counting एल्गोरिद्म में इसका अर्थ यह होता कि हमें ऐसा कोई मान नहीं मिला, जिसका हैश चार है, जो सत्य नहीं है।
इसलिए हम एल्गोरिद्म को ऐसे बदलते हैं कि अधिकतम मानों की सरणी में वह शून्यों वाले सबसे लंबे प्रत्यय की लंबाई नहीं, बल्कि “दाईं ओर से पहले 1” का सूचकांक सहेजे (स्पष्टता के लिए — सूचकांक हम एक से गिनते हैं), जो शून्यों वाले प्रत्यय की लंबाई में एक जोड़ने के समान है। इससे यह सुनिश्चित होता है कि सूचकांक i पर शून्य का अर्थ है कि किसी भी मान का हैश i के बराबर नहीं है, और तब ऐसी सरणी हम linear counting के लिए प्रयोग कर सकते हैं।
HyperLogLog का कार्यान्वयन
क्रम से चलते हैं:
def alpha(num_buckets):
return (0.7213 / (1 + 1.079 / num_buckets))
फलन alpha परिकलित अनुमान के लिए संशोधन लौटाता है; यह हम पिछली बार से जानते हैं, केवल HyperLogLog में alpha का मान समूहों की संख्या पर निर्भर करता है।
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
वह फलन, जो संख्या के अंत में शून्य बिटों की संख्या लौटाता है।
def count_maxims(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash) + 1
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
return max_zeroes
वह फलन, जो सभी मानों से गुज़रता है, उन्हें num_buckets समूहों में बाँटता है और प्रत्येक समूह के लिए दाईं ओर से पहले 1 का सूचकांक (शून्यों वाले अधिकतम प्रत्यय की लंबाई धन एक) परिकलित करता है।
def linear_counting(number_of_ones, num_buckets):
number_of_zeros = num_buckets - number_of_ones
Z = float(number_of_zeros) / num_buckets
p = (-num_buckets) * log(Z)
return p
Linear counting एल्गोरिद्म के परिकलन के लिए थोड़ा बदला हुआ फलन।
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = count_maxims(values, k)
estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)
if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
return linear_counting(number_of_ones, num_buckets)
else:
return estimate
मुख्य फलन, जो सब कुछ जोड़ता है। पहले यह संशोधित LogLog से अनुमान परिकलित करता है; चौथी पंक्ति में समांतर माध्य के बजाय हरात्मक माध्य प्रयोग करता है, और अंत में Linear counting के रूप में संशोधन लागू करता है, यदि परिकलित अनुमान समूहों की संख्या के 2.5 गुने से कम हो (इस स्थिति में हम अपेक्षा करते हैं कि LogLog का मानक अनुमान Linear counting से खराब होगा) और यदि अधिकतम मानों की सरणी में कम से कम एक शून्य हो (केवल इकाइयों वाली सरणी Linear counting में प्रयोग नहीं की जा सकती, पिछला लेख देखिए)। और HyperLogLog के परिणाम कैसे हैं?
हम परीक्षण का कोड चलाते हैं, जो क्रमशः 10, 100, …, 10,00,000 गणनसंख्या वाले समुच्चयों की गणनसंख्या का अनुमान लगाएगा:
for x in range(1, 7):
num_values = 10**x
values = (str(uuid4()) for _ in xrange(num_values))
cardinality = estimate_cardinality(values, 14)
print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)
परिणाम:
Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408
हम देखते हैं कि परिणाम सही परिणाम से हमेशा एक प्रतिशत से कम विचलित हैं। और यह अच्छा है!
HyperLogLog के अन्य सुधार
HyperLogLog में कुछ और रोचक सुधार भी हुए हैं। बची हुई समस्याओं में से एक है मेमोरी की अधिक आवश्यकता। यह काफ़ी अजीब लगता है, क्योंकि पिछली बार हमने मेमोरी की आवश्यकता की खूब प्रशंसा की थी और परिकलित किया था कि अधिकतम मानों की सरणी सहेजने के लिए 768 बाइट पर्याप्त हैं। परंतु समस्या तब आती है, जब आप एक विशाल बहुसमुच्चय की नहीं, बल्कि समानांतर रूप से दसियों लाख छोटे बहुसमुच्चयों की गणनसंख्या गिनना चाहते हों, या जब आप अधिकतम मानों की इन परिकलित सरणियों को बाद के किसी काम के लिए डेटाबेस में रखना चाहते हों।
उदाहरण के लिए, यदि हम एक साथ 100 करोड़ बहुसमुच्चयों की गणनसंख्या गिनें, तो वर्तमान कार्यान्वयन के साथ हमें 100 करोड़ गुना 768 बाइट चाहिए, यानी 768 GB। एक ओर यह बुरा नहीं है … पर दूसरी ओर हम HyperLogLog को बेहतर ढंग से लागू कर सकते हैं।
विरल निरूपण (sparse)
मान लीजिए हम k=12 रखते हैं, यानी समूहों की पहचान के लिए 12 बिट प्रयोग करते हैं और इसलिए हमें हैश मानों के 212 भिन्न समूह मिलते हैं। एल्गोरिद्म की शुरुआत में हमें 4096 लंबाई की सरणी आवंटित करनी होगी (फलन count_maxims की पंक्ति 3 देखिए)। और मान लीजिए हमारे बहुसमुच्चय में तीन भिन्न अवयव हैं। इसका अर्थ है कि सरणी में तीन भिन्न स्थानों पर हम कोई मान रखेंगे और बाकी 4093 मान सरणी में शून्य रहेंगे; बाकी 4093 का हमने कोई उपयोग ही नहीं किया। यह बहुत कुशल नहीं है, है न?
ऐसी सरणी से बचने के लिए, जो अधिकतर शून्य और अप्रयुक्त है, फिर भी मेमोरी का कीमती हिस्सा घेरती है, हम शुरुआत में मानों को युग्मों [सूचकांक, मान] के रूप में सहेज सकते हैं। बेहतर समझ के लिए उदाहरण। यह सरणी
[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
हम मेमोरी के लिहाज़ से कहीं अधिक कुशलता से दो युग्मों के रूप में निरूपित कर सकते हैं:
[0, 7], [4, 12]
मेमोरी में ढेर सारी अप्रयुक्त जगह आवंटित रखने के बजाय हम धीरे-धीरे केवल उतनी जगह आवंटित कर सकते हैं, जितनी सचमुच चाहिए। इस निरूपण को हम sparse (विरल) कहते हैं। फिर भी किसी क्षण यह निरूपण सीधे सरणी में सहेजने से अधिक मेमोरी लेने लगेगा — तब हम विरल निरूपण को बिना किसी जानकारी के खोए सामान्य सरणी में बदल सकते हैं।
ऑफ़सेट
व्यवहार में देखा गया है कि सरणी के सभी मान लगभग समान होते हैं। अधिकतम मानों की सरणी सामान्यतः, उदाहरण के लिए, ऐसी दिखती है:
[12, 13, 11, 13, 15, 12, 14, 11, 12, ..., 13, 14, 11]
सभी मान संख्या 13 के आसपास हैं। ऐसी सरणी का आकार घटाने की एक और रणनीति है प्रत्येक अवयव में से कोई निश्चित मान घटाना और उसे याद रखना। उदाहरण के लिए, हम आठ घटा सकते हैं:
[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]
अब सरणी का प्रत्येक मान मेमोरी में कम जगह लेता है — पहली सरणी में हमें 0 से 15 तक की संख्याएँ सहेजनी हैं, जिनके लिए 4 बिट चाहिए, जबकि दूसरी सरणी के लिए 3 बिट पर्याप्त हैं, क्योंकि हम केवल 0 से 7 तक की संख्याएँ सहेजते हैं। स्वाभाविक है कि इसके लिए सरणी का कार्यान्वयन अलग-अलग बिटों के स्तर पर होना चाहिए। जब हम सरणी से मान पढ़ना चाहें, तो उनमें याद रखा गया मान वापस जोड़ना होगा।
…और ढेर सारे अन्य सुधार। इस क्षेत्र में शोध अभी भी चल रहा है, इसलिए हम निश्चित रूप से और रोचक विचारों की प्रतीक्षा कर सकते हैं। अगली बार हम HyperLogLog सदिशों के सम्मिलन और सर्वनिष्ठ के बारे में बात करेंगे, और निकट भविष्य में किसी समय यह देखेंगे कि अरबों HyperLogLog सदिश सहेजना हमारे काम क्यों आ सकता है।
लिंक और स्रोत
- मेरा पूरा कार्यान्वयन आप GitHub पर देख सकते हैं।
- HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — वह पहला लेख, जिसमें HyperLogLog प्रस्तुत किया गया था।
- HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — HyperLogLog का सुधरा हुआ रूप, उदाहरण के लिए ऊपर बताए गए विरल निरूपण के साथ।
विषय-सूची: Linear counting: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, Min Value: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, LogLog: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, HyperLogLog: भिन्न मानों की संख्या का बहुत सटीक अनुमान कैसे लगाएँ