مرشح بلوم

فلتر بلوم هو هيكل أو بنية بيانات احتمالية موفرة للمساحة.[1] أوجدها بورتون هاوارد بلوم عام 1970وهي تستخدم لاختبار انتماء عنصر لمجموعة من عدمه. يمكن لفلتر بلوم أن يصنف عناصر خطأً على أنها تنتمي لمجموعة، إلا أنه لا تكون إجابته خاطئة أبدا إذا أجاب بعدم وجود العنصر في المجموعة. بمعنى آخر، تجاب الاستعلامات إما بـ«يحتمل أن ينتمي للمجموعة» أو «حتما لا ينتمي للمجموعة». يمكن إضافة عناصر للمجموعة لكن لا يمكن حذفها (لكن هناك حل لذلك مع فلتر «عادّ»). كلما زادت عناصر المجموعة كلما زاد احتمال التصنيفات الإيجابية الخاطئة (إجابة «يحتمل أن ينتمي للمجموعة»).

اقترح بلوم هذه الطريقة للتطبيقات التي تستخدم بيانات ضخمة الحجم يصعب معها استخدام تقنيات خوارزميات التجزئة التقليدية. ضرب مثلا بخوارزمية وضع شارطة في الكلمات الإنجليزية لقاموس يحوي نصف مليون كلمة، 90% منها تتبع قواعد شارطة بسيطة، بينما الـ10% المتبقية تحتاج إلى وصول كثيف للقرص الصلب لجلب أنماط وضع شارطة خاصة. إذا توفرت ذاكرة كافية فيمكن استخدام خوارزمية خالية من الإجابات الخاطئة لتفادي الوصول الغير ضروري للقرص. أما إذا كانت الذاكرة محدودة، فطريقة بلوم تستخدم ذاكرة أقل مع تمكنها من استبعاد معظم الوصول الغير ضروري للقرص. على سبيل المثال، مساحة تعادل 15% مما يُستخدم عادة في خوارزميات التجزئة المعتادة الخالية من الإجابات الخاطئة تحول دون 85% من الوصول للقرص، مثلما ينص مبدأ باريتو لكن هذه المرة 85-15.

بشكل عام، أقل من 10 بت لكل عنصر مطلوبة لاحتمالات أجوبة خاطئة تبلغ 1%، بغض النظر عن حجم أو عدد العناصر في المجموعة.