HyperLogLog: ভিন্ন ভিন্ন মানের সংখ্যা খুব নির্ভুলভাবে কীভাবে আনুমানিক নির্ণয় করা যায়
মাল্টিসেটে ভিন্ন ভিন্ন মানের সংখ্যা আনুমানিক নির্ণয়ের অ্যালগরিদম নিয়ে সিরিজটি এগিয়ে চলেছে state of the art অ্যালগরিদম HyperLogLog নিয়ে এই প্রবন্ধে। তবে এই অ্যালগরিদমের পেছনের সব ভাবনাই এসেছে আগে বর্ণিত LogLog থেকে, তাই আরও পড়তে চাইলে নিশ্চিত হয়ে নাও যে LogLog তুমি ভালোভাবে জান।
LogLog অ্যালগরিদমের দুইটি প্রধান সমস্যা ছিল:
বহিঃস্থ মান
LogLog এর চূড়ান্ত আনুমানিক মান বহিঃস্থ মানের (outlier) প্রতি খুব সংবেদনশীল, অর্থাৎ এমন মানের প্রতি, যা বাকি মানগুলো থেকে অনেক দূরে। সাধারণত দেখা যায়, প্রত্যেক গুচ্ছের শূন্য সাফিক্সের বৃহত্তম দৈর্ঘ্যগুলোর বেশির ভাগ প্রায় সমান, যেমন 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, 0, 1, 1, 1, 0]
এখন Linear counting অ্যালগরিদম প্রয়োগ করে এর সাহায্যে কার্ডিনালিটি আনুমানিক নির্ণয় করা যায়।
তবে এতে একটি গোলমাল আছে। আমরা অ্যারেতে রাখি বৃহত্তম শূন্য সাফিক্স, কিন্তু কোনো গুচ্ছের সব হ্যাশ মান যদি এক দিয়ে শেষ হয়? যেমন, হ্যাশ মান কোন গুচ্ছের তা চিহ্নিত করতে শেষ তিনটি বিট ব্যবহার করলে এই হ্যাশ মান “01001100” এর শূন্য সাফিক্সের দৈর্ঘ্য হতো শূন্য, কারণ ভেক্টর “01001” শেষ হয় এক দিয়ে। তাই বৃহত্তম মানের অ্যারেতে সূচক 4 এ (1002=410) রাখতাম শূন্য। কিন্তু linear counting অ্যালগরিদমে এর অর্থ দাঁড়াত, আমরা এমন কোনো মান পাইনি যার হ্যাশ মান চার, যা সত্য নয়।
তাই অ্যালগরিদমটি এমনভাবে বদলাই, যেন বৃহত্তম মানের অ্যারেতে দীর্ঘতম শূন্য সাফিক্সের দৈর্ঘ্য না রেখে রাখে “ডান দিক থেকে প্রথম এক” এর সূচক (প্রসঙ্গত, সূচক শুরু করি এক থেকে)। এটি শূন্য সাফিক্সের দৈর্ঘ্যের সঙ্গে এক যোগ করার সমান। এতে নিশ্চিত হয় যে সূচক 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 টি গুচ্ছে ভাগ করে এবং প্রত্যেক গুচ্ছের জন্য ডান দিক থেকে প্রথম এক এর সূচক (বৃহত্তম শূন্য সাফিক্সের দৈর্ঘ্য যোগ এক) নির্ণয় করে।
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 কোটি মাল্টিসেটের কার্ডিনালিটি নির্ণয় করলে বর্তমান বাস্তবায়নে লাগত 1,00,00,00,000 গুণ 768 বাইট, অর্থাৎ 768 GB। একদিক থেকে এটি খারাপ নয়… কিন্তু অন্যদিকে HyperLogLog আমরা আরও ভালোভাবে বাস্তবায়ন করতে পারি।
স্পার্স উপস্থাপন
ধরি আমরা k=12 ঠিক করি, অর্থাৎ গুচ্ছ চিহ্নিত করতে 12 টি বিট ব্যবহার করি, ফলে হ্যাশ মানের 212 টি ভিন্ন গুচ্ছ পাই। অ্যালগরিদমের শুরুতে আমাদের 4096 দৈর্ঘ্যের একটি অ্যারে তৈরি করতে হয় (দেখ ফাংশন count_maxims এর তৃতীয় লাইন)। আর ধরা যাক, আমাদের মাল্টিসেটে তিনটি ভিন্ন উপাদান আছে। তার মানে অ্যারের তিনটি ভিন্ন জায়গায় কোনো মান বসাব, আর অ্যারের বাকি 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: ভিন্ন ভিন্ন মানের সংখ্যা খুব নির্ভুলভাবে কীভাবে আনুমানিক নির্ণয় করা যায়