ব্লুম ফিল্টার গণনা

মৌলিক ধারণা

একটি কাউন্টিং ব্লুম ফিল্টারকে ব্লুম ফিল্টারের একটি সাধারণ ডেটা স্ট্রাকচার হিসাবে সংজ্ঞায়িত করা হয় যা উপাদানগুলির একটি ক্রম দেওয়া হলে একটি প্রদত্ত উপাদানের গণনা সংখ্যা একটি প্রদত্ত থ্রেশহোল্ডের চেয়ে কম কিনা তা পরীক্ষা করার জন্য প্রয়োগ করা হয়। একটি সাধারণ রূপ হিসাবে, ব্লুম ফিল্টারে মিথ্যা ইতিবাচক মিলের সম্ভাবনা রয়েছে, তবে মিথ্যা নেতিবাচক হওয়ার কোন সম্ভাবনা নেই – অন্য কথায়, একটি প্রশ্ন "সম্ভবত থ্রেশহোল্ডের চেয়ে বেশি বা সমান" বা "প্রান্তের চেয়ে অবশ্যই কম" ফেরত দেয়।

অ্যালগরিদম বর্ণনা

বেশিরভাগ প্যারামিটার, ব্লুম ফিল্টার গণনার অধীনে ব্যবহৃত হয়, ব্লুম ফিল্টারের সাথে একইভাবে সংজ্ঞায়িত করা হয়, যেমন n, k। m কে কাউন্টিং ব্লুম ফিল্টারে কাউন্টারের সংখ্যা হিসাবে চিহ্নিত করা হয়, যা ব্লুম ফিল্টারে m বিটের প্রসারণ।
একটি খালি কাউন্টিং ব্লুম ফিল্টার একটি m কাউন্টার হিসাবে সেট করা হয়েছে, সবগুলি 0-তে আরম্ভ করা হয়েছে৷
ব্লুম ফিল্টারের মতো, সেখানেও k বিভিন্ন হ্যাশ ফাংশন সংজ্ঞায়িত করা আবশ্যক, যার প্রত্যেকটি এম কাউন্টার অ্যারে অবস্থানগুলির একটিতে কিছু সেট উপাদান ম্যাপ বা হ্যাশ করার জন্য দায়ী, একটি অভিন্ন এলোমেলো বিতরণ তৈরি করে৷ এটিও একই যে k হল একটি ধ্রুবক, m থেকে অনেক কম, যা যোগ করা উপাদানগুলির সংখ্যার সমানুপাতিক৷
ব্লুম ফিল্টারের প্রধান সাধারণীকরণ হল একটি উপাদান যুক্ত করা। একটি উপাদান যুক্ত করতে, k হ্যাশ ফাংশনগুলির প্রতিটিতে k অ্যারে অবস্থানগুলি পেতে এবং এই সমস্ত অবস্থানে কাউন্টার 1 বৃদ্ধি করতে এটি সন্নিবেশ করুন৷
একটি থ্রেশহোল্ড θ সহ একটি উপাদানের জন্য অনুসন্ধান করতে (একটি উপাদানের গণনা সংখ্যা θ-এর চেয়ে কম কিনা তা যাচাই করতে), k কাউন্টার অবস্থানগুলি পেতে প্রতিটি k হ্যাশ ফাংশনে এটি সন্নিবেশ করুন৷
যদি এই অবস্থানের কোনো কাউন্টার θ-এর থেকে ছোট হয়, তাহলে উপাদানের গণনা সংখ্যা অবশ্যই θ-এর থেকে ছোট - যদি এটি উচ্চতর এবং সমান হত, তাহলে সমস্ত সংশ্লিষ্ট কাউন্টারগুলি θ-এর চেয়ে বেশি বা সমান হত৷
যদি সবগুলি θ-এর সমান বা উচ্চতর হয়, তাহলে হয় গণনাটি সত্যিই বেশি বা θ এর সমান, অথবা কাউন্টারগুলি দৈবক্রমে উচ্চতর বা θ এর সমান।
যদি সবগুলো θ-এর থেকে বেশি বা সমান হয় যদিও গণনা θ-এর থেকে কম হয়, এই পরিস্থিতিটিকে মিথ্যা ইতিবাচক হিসাবে সংজ্ঞায়িত করা হয়। ব্লুম ফিল্টারের মতো, এটিও কম করা উচিত।