- আমরা প্রথমে একটি মেমরি ব্লক নির্বাচন করি৷
- তারপর আমরা প্রতিটি ব্লকের মধ্যে স্থানীয় ব্লুম ফিল্টার নির্বাচন করি।
- এটি মেমরি ব্লকের মধ্যে ভারসাম্যহীনতার কারণ হতে পারে
- এই ফিল্টারটি দক্ষ, কিন্তু খারাপ মিথ্যা পজিটিভ রেট(FPR)।
- প্রথম ক্ষেত্রে, ব্লক করা ব্লুম ফিল্টারগুলির একই আকারের স্ট্যান্ডার্ড ব্লুম ফিল্টারগুলির মতো একই FPR (ফলস পজিটিভ রেট) থাকা উচিত৷
- অবরুদ্ধ ব্লুম ফিল্টারটি স্ট্যান্ডার্ড ব্লুম ফিল্টার (ব্লুম ফিল্টার ব্লক) থেকে তুলনামূলকভাবে কম ব্লক বি এর একটি ক্রম নিয়ে গঠিত, যার প্রতিটি একটি ক্যাশে-লাইনে ফিট করে।
- ব্লকড ব্লুম ফিল্টার স্কিম পার্টিশন স্কিম থেকে আলাদা করা হয়, যেখানে প্রতিটি বিট আলাদা ব্লকে ঢোকানো হয়।
ব্লকড ব্লুম ফিল্টার নিম্নলিখিত উপায়ে প্রয়োগ করা হয় -
বিট প্যাটার্নস (প্যাট)
এই বিষয়ে, আমরা প্রি-কম্পিউটেড বিট প্যাটার্ন প্রয়োগ করে ব্লক করা ব্লুম ফিল্টার বাস্তবায়নের জন্য আলোচনা করি। k হ্যাশ ফাংশনগুলির মূল্যায়নের মাধ্যমে k বিট সেট করার পরিবর্তে, একটি একক হ্যাশ ফাংশন বি প্রস্থের র্যান্ডম k-বিট প্যাটার্নের একটি টেবিল থেকে একটি পূর্বনির্ধারিত প্যাটার্ন নির্বাচন করে। অনেক ক্ষেত্রে, এই টেবিলটি ক্যাশে ফিট হবে। এই সমাধানের সাথে, শুধুমাত্র একটি ছোট (বিটের পরিপ্রেক্ষিতে) হ্যাশ মান প্রয়োজন, এবং অপারেশনটি কয়েকটি SIMD (একক নির্দেশ মাল্টিপল ডেটা) নির্দেশাবলী ব্যবহার করে বাস্তবায়ন করা যেতে পারে। ব্লুম ফিল্টার স্থানান্তর করার সময়, টেবিলটিকে ডেটাতে স্পষ্টভাবে অন্তর্ভুক্ত করার প্রয়োজন নেই, তবে বীজের মান প্রয়োগ করে পুনর্গঠন করা যেতে পারে।
বিট প্যাটার্ন পদ্ধতির প্রধান অসুবিধা হল যে দুটি উপাদান একই প্যাটার্নে হ্যাশ করার সময় টেবিলের সংঘর্ষের কারণ হতে পারে। এটি FPR বৃদ্ধির কারণ।
মাল্টিপ্লেক্সিং প্যাটার্নস
এই ধারণাটিকে আরও একবার পরিমার্জিত করার জন্য, আমরা একটি টেবিল থেকে বিটওয়াইজ-অথবা-এক্স প্যাটার্নের মাধ্যমে গড় সংখ্যক k/x সেট বিট সহ বিভিন্ন ধরনের প্যাটার্ন অর্জন করতে পারি।
মাল্টি-ব্লকিং
আরও একটি বৈকল্পিক যা এফপিআর উন্নত করতে সাহায্য করে, তাকে মাল্টি-ব্লকিং বলা হয়। আমরা X ব্লুম ফিল্টার ব্লক অ্যাক্সেস করার জন্য ক্যোয়ারী অপারেশনের অনুমতি দিই, প্রতিটি ব্লকে যথাক্রমে k/X বিট সেট বা পরীক্ষা করে। (যখন k X দ্বারা বিভাজ্য হয় না, আমরা প্রথম k মোড X ব্লকগুলিতে একটি অতিরিক্ত বিট সেট করি।) মাল্টি-ব্লকিং ব্লকের আকারকে XB (B- প্রতিটি ব্লকের আকার) তে বাড়ানোর চেয়ে ভাল কাজ করে, যেহেতু আরও বৈচিত্র্য এটি চালু করা হয়েছে উপায় যদি আমরা সেট বিটগুলিকে কয়েকটি ব্লকের মধ্যে ভাগ করি, প্রতি ব্লকে 1 বিটের প্রত্যাশিত সংখ্যা একই থাকে। যাইহোক, একটি উপাদান অ্যাক্সেস করার সময় প্রতিটি অংশগ্রহণকারী ব্লকে শুধুমাত্র k/X বিট বিবেচনা করা হয়।
