مرشح التوهج

في مجال الحوسبة ، يُعدّ مرشح بلوم بنية بيانات احتمالية فعّالة من حيث المساحة ، ابتكرها بيرتون هوارد بلوم عام 1970، وتُستخدم لاختبار ما إذا كان عنصر ما ينتمي إلى مجموعة . من الممكن حدوث نتائج إيجابية خاطئة ، ولكن لا توجد نتائج سلبية خاطئة - بمعنى آخر، تُرجع الاستعلامات إما "ربما ينتمي إلى المجموعة" أو "بالتأكيد ليس ينتمي إلى المجموعة". يمكن إضافة عناصر إلى المجموعة، ولكن لا يمكن حذفها (مع إمكانية معالجة ذلك باستخدام متغير مرشح بلوم العدّي )؛ وكلما زاد عدد العناصر المضافة، زاد احتمال النتائج الإيجابية الخاطئة.

اقترح بلوم هذه التقنية للتطبيقات التي تتطلب فيها كمية البيانات المصدرية حجمًا هائلاً من الذاكرة، وهو أمر غير عملي في حال تطبيق تقنيات التجزئة "التقليدية" الخالية من الأخطاء . وقدّم مثالًا على خوارزمية تقسيم الكلمات إلى مقاطع لقاموس يحتوي على 500,000 كلمة، حيث يتبع 90% منها قواعد تقسيم بسيطة، بينما تتطلب النسبة المتبقية (10%) عمليات وصول مكلفة إلى القرص لاسترجاع أنماط تقسيم محددة. مع توفر ذاكرة كافية ، يمكن استخدام تجزئة خالية من الأخطاء للتخلص من جميع عمليات الوصول غير الضرورية إلى القرص؛ من ناحية أخرى، مع ذاكرة محدودة، تستخدم تقنية بلوم مساحة تجزئة أصغر، لكنها مع ذلك تُقلل من معظم عمليات الوصول غير الضرورية. على سبيل المثال، مساحة تجزئة لا تتجاوز 18% من الحجم المطلوب لتجزئة مثالية خالية من الأخطاء، لا تزال تُقلل من 87% من عمليات الوصول إلى القرص. ^{[ 1 ]}

وبشكل عام، يلزم أقل من 10 بتات لكل عنصر لتحقيق احتمال خطأ إيجابي بنسبة 1%، بغض النظر عن حجم أو عدد العناصر في المجموعة. ^{[ 2 ]}

وصف الخوارزمية

مرشح بلوم الفارغ عبارة عن مصفوفة بتات مكونة من $m$ بت، جميعها مضبوطة على الصفر. وهو مزود بـ $k$ دالة تجزئة مختلفة ، تقوم كل منها بربط عناصر المجموعة بأحد المواضع $m$ الممكنة في المصفوفة. ولتحقيق الأداء الأمثل، يجب أن تكون دوال التجزئة موزعة توزيعًا منتظمًا ومستقلة . عادةً، $k$ ثابت صغير يعتمد على معدل الخطأ المطلوب $ε$ ، بينما $m$ يتناسب طرديًا مع $k$ وعدد العناصر المراد إضافتها.

لإضافة عنصر، قم بتمريره إلى كل دالة من دوال التجزئة $k$ للحصول على $k$ موضعًا في المصفوفة. اضبط البتات في جميع هذه المواضع على 1.

لاختبار ما إذا كان عنصر ما موجودًا في المجموعة، يُمرر إلى كل دالة من دوال التجزئة $k$ للحصول على k $موضعًا$ في المصفوفة. إذا كانت أي من البتات في هذه المواضع تساوي صفرًا، فإن العنصر بالتأكيد ليس في المجموعة؛ أما إذا كان موجودًا، فستكون جميع البتات قد عُدّلت إلى 1 عند إدخاله. إذا كانت جميع البتات تساوي 1، فإما أن العنصر موجود في المجموعة، أو أن البتات قد عُدّلت بالصدفة إلى 1 أثناء إدخال عناصر أخرى، مما ينتج عنه نتيجة إيجابية خاطئة . في مرشح بلوم البسيط، لا توجد طريقة للتمييز بين الحالتين، ولكن يمكن للتقنيات الأكثر تقدمًا معالجة هذه المشكلة.

قد يكون شرط تصميم $k من دوال التجزئة المستقلة المختلفة مكلفًا للغاية عند$ $قيم k$ الكبيرة . وللحصول على دالة تجزئة جيدة ذات مخرجات واسعة، ينبغي أن يكون هناك ارتباط ضئيل، إن وجد، بين حقول البت المختلفة لهذه الدالة، لذا يمكن استخدام هذا النوع من التجزئة لتوليد دوال تجزئة "مختلفة" متعددة عن طريق تقسيم مخرجاتها إلى حقول بت متعددة. بدلاً من ذلك، يمكن تمرير $k$ من القيم الأولية المختلفة (مثل 0، 1، ...، $k$ - 1) إلى دالة تجزئة تأخذ قيمة أولية؛ أو إضافة هذه القيم إلى المفتاح. بالنسبة لقيم $m$ و/أو $k$ الكبيرة ، يمكن تخفيف شرط الاستقلالية بين دوال التجزئة مع زيادة طفيفة في معدل النتائج الإيجابية الخاطئة. ^[³^] (على وجه التحديد، يُظهر ديلينجر ومانوليوس (2004ب) فعالية اشتقاق مؤشرات $k$ باستخدام التجزئة المزدوجة المحسّنة والتجزئة الثلاثية ، وهما نوعان من التجزئة المزدوجة يُعتبران في الواقع مولدات أرقام عشوائية بسيطة مُهيأة بقيمتي التجزئة أو الثلاث).

يستحيل إزالة عنصر من مرشح بلوم البسيط هذا، لعدم وجود طريقة لتحديد أي من البتات $k$ التي يُمثلها العنصر يجب مسحها. مع أن ضبط أي من هذه البتات $k$ على الصفر يكفي لإزالة العنصر، إلا أنه سيؤدي أيضًا إلى إزالة أي عناصر أخرى تُمثله. ولأن الخوارزمية البسيطة لا تُتيح تحديد ما إذا كانت هناك عناصر أخرى قد أُضيفت وتؤثر على البتات الخاصة بالعنصر المراد إزالته، فإن مسح أي من هذه البتات قد يُؤدي إلى نتائج سلبية خاطئة.

يمكن محاكاة إزالة عنصر لمرة واحدة من مرشح بلوم باستخدام مرشح بلوم ثانٍ يحتوي على العناصر التي تمت إزالتها. مع ذلك، تتحول النتائج الإيجابية الخاطئة في المرشح الثاني إلى نتائج سلبية خاطئة في المرشح المركب، وهو أمر غير مرغوب فيه. في هذه الطريقة، لا يمكن إعادة إضافة عنصر تمت إزالته سابقًا، إذ يتطلب ذلك إزالته من مرشح "العناصر التي تمت إزالتها".

في كثير من الأحيان، تكون جميع المفاتيح متاحة، لكن تعدادها مكلف (على سبيل المثال، يتطلب قراءة العديد من البيانات من القرص). عندما يرتفع معدل الإنذارات الكاذبة بشكل كبير، يمكن إعادة إنشاء المرشح؛ وهذا نادر الحدوث نسبيًا.

مزايا المكان والزمان

على الرغم من احتمالية وجود نتائج إيجابية خاطئة، تتميز مرشحات بلوم بميزة كبيرة في توفير المساحة مقارنةً بهياكل البيانات الأخرى لتمثيل المجموعات، مثل أشجار البحث الثنائية ذاتية التوازن ، وجداول البحث الثنائية ، وجداول التجزئة ، أو المصفوفات البسيطة أو القوائم المرتبطة . تتطلب معظم هذه الهياكل تخزين عناصر البيانات نفسها على الأقل، وهو ما قد يتطلب عددًا قليلًا من البتات، للأعداد الصحيحة الصغيرة، إلى عدد كبير من البتات، كما هو الحال مع السلاسل النصية ( تُستثنى جداول البحث الثنائية لأنها تسمح بمشاركة المساحة بين العناصر ذات البادئات المتساوية). مع ذلك، لا تخزن مرشحات بلوم عناصر البيانات على الإطلاق، ويجب توفير حل منفصل للتخزين الفعلي. تُضيف الهياكل المرتبطة عبئًا إضافيًا خطيًا على المساحة للمؤشرات. في المقابل، يتطلب مرشح بلوم ذو نسبة خطأ 1% وقيمة مثلى لـ $k$ حوالي 9.6 بت فقط لكل عنصر، بغض النظر عن حجم العناصر. تأتي هذه الميزة جزئيًا من صغر حجمه، الموروث من المصفوفات، وجزئيًا من طبيعته الاحتمالية. يمكن تقليل معدل النتائج الإيجابية الخاطئة بنسبة 1% بمقدار عشرة أضعاف عن طريق إضافة حوالي 4.8 بت فقط لكل عنصر.

مع ذلك، إذا كان عدد القيم المحتملة صغيرًا، وكان من الممكن أن يكون العديد منها ضمن المجموعة، فإن مرشح بلوم يُتجاوز بسهولة بواسطة مصفوفة البتات الحتمية، التي لا تتطلب سوى بت واحد لكل عنصر محتمل. تكتسب جداول التجزئة ميزة في المساحة والوقت إذا بدأت بتجاهل التصادمات وتخزين ما إذا كانت كل خانة تحتوي على مدخل فقط؛ في هذه الحالة ، تصبح فعليًا مرشحات بلوم مع $k = 1.$ ^{[ 4 ]}

تتميز مرشحات بلوم بخاصية فريدة، وهي أن الوقت اللازم لإضافة عناصر أو للتحقق من وجود عنصر في المجموعة هو ثابت $O(k)$ ، ولا يعتمد إطلاقًا على عدد العناصر الموجودة في المجموعة. لا توجد بنية بيانات أخرى للمجموعات ذات المساحة الثابتة تتمتع بهذه الخاصية، ولكن متوسط زمن الوصول لجداول التجزئة المتفرقة قد يجعلها أسرع عمليًا من بعض مرشحات بلوم. مع ذلك، في التطبيقات البرمجية، يتفوق مرشح بلوم لأن عمليات البحث $k$ فيه مستقلة وقابلة للتوازي.

لفهم كفاءة استخدام المساحة، من المفيد مقارنة مرشح بلوم العام بحالته الخاصة عندما $k = 1.$ إذا كانت $k = 1$ ، فإنه للحفاظ على معدل الإنذارات الكاذبة منخفضًا بما يكفي، يجب ضبط نسبة صغيرة من البتات، مما يعني أن المصفوفة يجب أن تكون كبيرة جدًا وتحتوي على سلاسل طويلة من الأصفار. محتوى المعلومات في المصفوفة منخفض بالنسبة لحجمها. يسمح مرشح بلوم المعمم ( $k$ أكبر من 1) بضبط عدد أكبر بكثير من البتات مع الحفاظ على معدل إنذارات كاذبة منخفض؛ إذا تم اختيار المعاملات ( $k$ و $m$ ) بشكل جيد، فسيتم ضبط حوالي نصف البتات، ^{[ 5 ]} وستكون هذه البتات عشوائية ظاهريًا، مما يقلل التكرار ويزيد محتوى المعلومات.

احتمالية النتائج الإيجابية الخاطئة

لنفترض أن دالة التجزئة تختار كل موضع في المصفوفة باحتمالية متساوية. إذا كان m هو عدد البتات في المصفوفة، فإن احتمال عدم تعيين بت معين إلى 1 بواسطة دالة تجزئة معينة أثناء إدخال عنصر ما هو

1-{\frac {1}{m}}.

إذا كان k هو عدد دوال التجزئة، ولم يكن هناك ارتباط كبير بينها، فإن احتمال عدم ضبط البت على 1 بواسطة أي من دوال التجزئة هو

\left(1-{\frac {1}{m}}\right)^{k}.

يمكننا استخدام المتطابقة المعروفة لـ e ^{− 1}

\lim _{m\to \infty }\left(1-{\frac {1}{m}}\right)^{m}={\frac {1}{e}}

لنستنتج أنه بالنسبة لقيم m الكبيرة ،

\left(1-{\frac {1}{m}}\right)^{k}=\left(\left(1-{\frac {1}{m}}\right)^{m}\right)^{k/m}\approx e^{-k/m}.

إذا أدخلنا n عنصرًا، فإن احتمال أن تظل قيمة بت معين تساوي 0 هو

\left(1-{\frac {1}{m}}\right)^{kn}\approx e^{-kn/m};

وبالتالي فإن احتمال أن يكون الناتج 1 هو

1-\left(1-{\frac {1}{m}}\right)^{kn}\approx 1-e^{-kn/m}.

الآن، اختبر انتماء عنصر غير موجود في المجموعة. كل موضع من مواضع المصفوفة k المحسوبة بواسطة دوال التجزئة يساوي 1 باحتمالية كما سبق. غالبًا ما تُعطى احتمالية أن تكون جميعها 1، مما سيؤدي إلى ادعاء الخوارزمية خطأً أن العنصر موجود في المجموعة، على النحو التالي:

\varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.

هذا ليس دقيقًا تمامًا لأنه يفترض استقلال احتمالات ضبط كل بت. مع ذلك، بافتراض أنه تقريب جيد، نجد أن احتمال النتائج الإيجابية الخاطئة يتناقص مع ازدياد قيمة m (عدد البتات في المصفوفة)، ويزداد مع ازدياد قيمة n (عدد العناصر المُضافة).

الاحتمال الحقيقي لنتيجة إيجابية خاطئة، دون افتراض الاستقلال، هو

{\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{{kn \atop i}\right\}

حيث تشير الأقواس المعقوفة { إلى أعداد ستيرلينغ من النوع الثاني . ^{[ 6 ]}

يقدم ميتزنماخر وأوبفال تحليلًا بديلًا يصل إلى نفس التقريب دون افتراض الاستقلال. ^{[ 7 ]} بعد إضافة جميع العناصر n إلى مرشح بلوم، لنفترض أن q هي نسبة البتات m التي تم ضبطها على 0. (أي أن عدد البتات التي لا تزال مضبوطة على 0 هو qm ). عندئذٍ، عند اختبار انتماء عنصر غير موجود في المجموعة، بالنسبة لموضع المصفوفة المحدد بواسطة أي من دوال التجزئة k ، فإن احتمال أن يكون البت مضبوطًا على 1 هو $1-q$ إذن، احتمال أن تجد جميع دوال التجزئة k بتاتها مضبوطة على 1 هو $(1-q)^{k}$ علاوة على ذلك ، فإن القيمة المتوقعة لـ q هي احتمال أن يبقى موضع معين في المصفوفة دون تغيير بواسطة كل دالة من دوال التجزئة k لكل عنصر من العناصر n ، وهو (كما سبق)

E[q]=\left(1-{\frac {1}{m}}\right)^{kn}

.

من الممكن إثبات، دون افتراض الاستقلال، أن قيمة q تتركز بشدة حول قيمتها المتوقعة. وعلى وجه الخصوص، من خلال متباينة أزوما-هوفدينغ ، يثبتون أن ^{[ 8 ]}

\Pr(\left|qE[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-2\lambda ^{2}/kn)

وبناءً على ذلك، يمكننا القول إن الاحتمال الدقيق للنتائج الإيجابية الخاطئة هو

\sum _{t}\Pr(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}

كما كان من قبل.

العدد الأمثل لدوال التجزئة

يجب أن يكون عدد دوال التجزئة، k ، عددًا صحيحًا موجبًا. وبغض النظر عن هذا القيد، فإنه بالنسبة لقيمتين معطيتين لـ m و n ، تكون قيمة k التي تقلل من احتمالية النتائج الإيجابية الخاطئة هي

k={\frac {m}{n}}\ln 2.

يمكن حساب عدد البتات المطلوبة، m ، بمعلومية n (عدد العناصر المُدخلة) واحتمالية الخطأ الإيجابي المطلوبة ε (وبافتراض استخدام القيمة المثلى لـ k ) عن طريق استبدال القيمة المثلى لـ k في تعبير الاحتمالية أعلاه:

\varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac {m}{n}}\ln 2}=\left({\frac {1}{2}}\right)^{{\frac {m}{n}}\ln 2}

والتي يمكن تبسيطها إلى:

\ln(\varepsilon )=-{\frac {m}{n}}\ln(2)^{2}.

وهذا ينتج عنه:

m=-{\frac {n\ln(\varepsilon )}{\ln(2)^{2}}}

إذن، العدد الأمثل للبتات لكل عنصر هو

{\frac {m}{n}}=-{\frac {\ln(\varepsilon )}{\ln(2)^{2}}}\approx -2.08\ln(\varepsilon )

مع العدد المقابل من دوال التجزئة k (مع تجاهل التكامل):

k=-{\frac {\ln(\varepsilon )}{\ln(2)}}.

هذا يعني أنه بالنسبة لاحتمالية إيجابية خاطئة معينة ε ، فإن طول مرشح بلوم m يتناسب مع عدد العناصر التي يتم ترشيحها n، ويعتمد عدد دوال التجزئة المطلوبة فقط على احتمالية الإيجابية الخاطئة المستهدفة ε . ^{[ 9 ]}

الصيغة $m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}$ هو تقريبي لثلاثة أسباب. أولاً، وهو الأقل أهمية، أنه تقريبي $1-{\frac {1}{m}}$ مثل $e^{-{\frac {1}{m}}}$ وهو تقريب تقاربي جيد (أي أنه ينطبق عندما m → ∞). ثانيًا، وهو ما يثير القلق أكثر، يفترض أنه أثناء اختبار العضوية، يكون حدث ضبط بت واحد مُختَبَر على 1 مستقلًا عن حدث ضبط أي بت مُختَبَر آخر على 1. ثالثًا، وهو الأمر الأكثر إثارة للقلق، يفترض أن $k={\frac {m}{n}}\ln 2$ وهو أمر متكامل بشكل غير متوقع.

ومع ذلك، يقدم غويل وغوبتا، ^{[ 10 ]} حدًا أعلى دقيقًا لا يقدم أي تقريبات ولا يتطلب أي افتراضات. يوضحان أن احتمال النتيجة الإيجابية الخاطئة لمرشح بلوم محدود ذي m بت ( $m>1$ ، و n عنصرًا، و k دالة تجزئة على الأكثر

\varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.

يمكن تفسير هذا الحد على أنه يعني أن الصيغة التقريبية $\left(1-e^{-{\frac {kn}{m}}}\right)^{k}$ يمكن تطبيق ذلك بعقوبة لا تتجاوز نصف عنصر إضافي ولا تتجاوز بت واحد أقل.

تقريب عدد العناصر في مرشح بلوم

يمكن تقريب عدد العناصر في مرشح بلوم باستخدام الصيغة التالية،

n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],

أين $n^{*}$ يمثل تقديرًا لعدد العناصر في المرشح، و m هو طول (حجم) المرشح، و k هو عدد دوال التجزئة، و X هو عدد البتات التي تم تعيينها إلى واحد. ^{[ 11 ]}

اتحاد وتقاطع المجموعات

تُعدّ مرشحات بلوم طريقةً لتمثيل مجموعة من العناصر بشكلٍ مُختصر. من الشائع محاولة حساب حجم التقاطع أو الاتحاد بين مجموعتين. يُمكن استخدام مرشحات بلوم لتقريب حجم التقاطع والاتحاد بين مجموعتين. بالنسبة لمرشحين من مرشحات بلوم بطول $m$ ، يُمكن تقدير عدد عناصرهما على التوالي كما يلي:

n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]

و

n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].

يمكن تقدير حجم اتحادهم على النحو التالي:

n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m}}\right],

أين $n(A\cup B)$ يمثل عدد البتات التي تم ضبطها على واحد في أي من مرشحي بلوم. وأخيرًا، يمكن تقدير التقاطع على النحو التالي:

n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),

باستخدام الصيغ الثلاث معًا. ^{[ 11 ]}

ملكيات

على عكس جدول التجزئة القياسي الذي يستخدم العنونة المفتوحة لحل التصادمات ، يمكن لمرشح بلوم ذي الحجم الثابت تمثيل مجموعة ذات عدد كبير من العناصر؛ ولا تفشل إضافة أي عنصر بسبب "امتلاء" بنية البيانات. مع ذلك، يزداد معدل النتائج الإيجابية الخاطئة باطراد مع إضافة العناصر حتى تُضبط جميع البتات في المرشح على 1، وعندها تُعطي جميع الاستعلامات نتيجة إيجابية. في تجزئة العنونة المفتوحة، لا تحدث نتائج إيجابية خاطئة أبدًا، لكن الأداء يتدهور باطراد حتى يقترب من البحث الخطي .
يمكن تنفيذ عمليتي الاتحاد والتقاطع لمرشحات بلوم ذات الحجم ومجموعة دوال التجزئة المتماثلة باستخدام عمليتي OR وAND على مستوى البتات ، على التوالي. عملية الاتحاد على مرشحات بلوم لا تُفقد البيانات، بمعنى أن مرشح بلوم الناتج هو نفسه مرشح بلوم الذي تم إنشاؤه من الصفر باستخدام اتحاد المجموعتين. أما عملية التقاطع، فتُحقق خاصية أضعف: احتمال الخطأ الإيجابي في مرشح بلوم الناتج لا يتجاوز احتمال الخطأ الإيجابي في أحد مرشحات بلوم المكونة له، ولكنه قد يكون أكبر من احتمال الخطأ الإيجابي في مرشح بلوم الذي تم إنشاؤه من الصفر باستخدام تقاطع المجموعتين.
يمكن اعتبار بعض أنواع الترميز المتراكب بمثابة مرشح بلوم مُنفذ باستخدام بطاقات ذات حواف مشقوقة . ومن الأمثلة على ذلك ترميز زاتوكودينج ، الذي ابتكره كالفن مويرز عام 1947، حيث تُمثل مجموعة الفئات المرتبطة بمعلومات معينة بشقوق على بطاقة، بنمط عشوائي من أربعة شقوق لكل فئة.

أمثلة

تستخدم ذبابات الفاكهة آلية مشابهة لمرشحات بلوم للكشف عن حداثة الروائح، مع وجود اختلافات أساسية تتمثل في اختبارات الحالة مثل تشابه الرائحة مع روائح سبق التعرض لها أو الوقت المنقضي منذ التعرض السابق لنفس الرائحة. ^{[ 12 ]}
تستخدم خوادم شركة أكاماي تكنولوجيز ، وهي شركة متخصصة في توصيل المحتوى ، مرشحات بلوم لمنع تخزين العناصر التي يطلبها المستخدمون مرة واحدة فقط في ذاكرة التخزين المؤقت على القرص. هذه العناصر هي كائنات ويب يطلبها المستخدمون مرة واحدة فقط، وقد وجدت أكاماي أن هذا ينطبق على ما يقرب من ثلاثة أرباع بنية التخزين المؤقت لديها. يؤدي استخدام مرشح بلوم لاكتشاف الطلب الثاني لعنصر ويب وتخزين هذا العنصر مؤقتًا عند الطلب الثاني فقط إلى منع هذه العناصر من دخول ذاكرة التخزين المؤقت على القرص، مما يقلل بشكل كبير من عبء العمل على القرص ويزيد من معدلات الوصول إلى ذاكرة التخزين المؤقت. ^{[ 13 ]}
تستخدم قواعد بيانات Google Bigtable و Apache HBase و Apache Cassandra و ScyllaDB و PostgreSQL ^{[ 14 ]} مرشحات بلوم لتقليل عمليات البحث على القرص عن الصفوف أو الأعمدة غير الموجودة. ويؤدي تجنب عمليات البحث المكلفة على القرص إلى تحسين أداء استعلامات قواعد البيانات بشكل ملحوظ. ^{[ 15 ]}
كان متصفح جوجل كروم يستخدم سابقًا مرشح بلوم لتحديد عناوين URL الضارة . كان يتم فحص أي عنوان URL أولًا باستخدام مرشح بلوم محلي، وإذا كانت نتيجة مرشح بلوم إيجابية، يتم إجراء فحص كامل للعنوان (مع تنبيه المستخدم إذا كانت النتيجة إيجابية أيضًا). ^[¹⁶^]^[¹⁷^]
يستخدم متصفح موزيلا فايرفوكس مرشحات بلوم المتتالية لإلغاء الشهادات ^{[ 18 ]}^{[ 19 ]} ولحظر الإضافات الضارة. ^{[ 20 ]}
يستخدم محرك البحث مايكروسوفت بينغ مرشحات بلوم الهرمية متعددة المستويات لفهرس البحث الخاص به، BitFunnel . وقد وفرت مرشحات بلوم تكلفة أقل من فهرس بينغ السابق، الذي كان يعتمد على الملفات المعكوسة . ^{[ 21 ]}
يستخدم Squid Web Proxy Cache مرشحات Bloom لتلخيص ذاكرة التخزين المؤقت ^. [ ²²^]
استخدمت عملة البيتكوين مرشحات بلوم لتسريع مزامنة المحفظة حتى تم اكتشاف ثغرات أمنية تتعلق بالخصوصية في تطبيق مرشحات بلوم. ^{[ 23 ]}
يستخدم نظام التخزين الأرشيفي Venti مرشحات Bloom للكشف عن البيانات المخزنة مسبقًا . ^{[ 24 ]}
يستخدم مدقق نموذج SPIN مرشحات بلوم لتتبع فضاء الحالة الذي يمكن الوصول إليه لمشاكل التحقق الكبيرة. ^{[ 25 ]}
يستخدم إطار عمل التحليلات المتتالية مرشحات بلوم لتسريع عمليات الربط غير المتماثل، حيث تكون إحدى مجموعات البيانات المربوطة أكبر بكثير من الأخرى (والتي تسمى غالبًا ربط بلوم في أدبيات قواعد البيانات). ^{[ 26 ]}
يستخدم وكيل نقل البريد Exim (MTA) مرشحات Bloom في ميزة تحديد معدل النقل.
يستخدم موقع Medium مرشحات بلوم لتجنب التوصية بالمقالات التي قرأها المستخدم مسبقًا. ^{[ 27 ]}
يستخدم إيثيريوم مرشحات بلوم للعثور بسرعة على السجلات في سلسلة كتل إيثيريوم .
يستخدم Grafana Tempo مرشحات بلوم لتحسين أداء الاستعلامات من خلال تخزين مرشحات بلوم لكل كتلة خلفية. ويتم الوصول إلى هذه المرشحات في كل استعلام لتحديد الكتل التي تحتوي على بيانات تتوافق مع معايير البحث المُقدمة ^{[ 28 ].}

البدائل

تستخدم مرشحات كلاسيك بلوم $1.44\log _{2}(1/\varepsilon )$ عدد البتات من المساحة لكل مفتاح مُدخل، حيث $\varepsilon$ يمثل معدل النتائج الإيجابية الخاطئة لمرشح بلوم. ومع ذلك، فإن المساحة الضرورية لأي بنية بيانات تؤدي نفس دور مرشح بلوم هي فقط $\log _{2}(1/\varepsilon )$ لكل مفتاح. ^{[ 29 ]} وبالتالي تستخدم مرشحات بلوم مساحة أكبر بنسبة 44٪ من بنية البيانات المثلى المكافئة.

يقدم باج وآخرون بنية بيانات تستخدم ${\textstyle (1+o(1))n\log _{2}(1/\epsilon )+O(n)}$ ^{[ 30}^] تدعم هذه التقنية البتات مع دعم عمليات ذات وقت متوقع ثابت. ^[ 30] هيكل بياناتها نظري في المقام الأول، ولكنه يرتبط ارتباطًا وثيقًا بمرشح القسمة واسع الاستخدام ، والذي يمكن ضبط معلمات له لاستخدامه في $(1+\delta )n\log \epsilon ^{-1}+3n$ بتات من الفضاء، لمعامل عشوائي $\delta >0$ مع تقديم الدعم $O(\delta ^{-2})$ العمليات الزمنية. ^{[ 31 ]} تشمل مزايا مرشح القسمة، عند مقارنته بمرشح بلوم، موضعية مرجعه وقدرته على دعم عمليات الحذف.

يُعدّ مرشح الوقواق بديلاً آخر لمرشح بلوم الكلاسيكي ، وهو يعتمد على متغيرات فعّالة من حيث المساحة لتجزئة الوقواق . في هذه الحالة، يتم إنشاء جدول تجزئة لا يحتوي على مفاتيح أو قيم، بل على بصمات قصيرة (تجزئات صغيرة) للمفاتيح. إذا عثر البحث عن المفتاح على بصمة مطابقة، فمن المحتمل أن يكون المفتاح موجودًا في المجموعة. تدعم مرشحات الوقواق عمليات الحذف، وتتميز بموقع مرجعي أفضل من مرشحات بلوم. ^{[ 32 ]} بالإضافة إلى ذلك، في بعض أنظمة المعلمات، يمكن ضبط معلمات مرشحات الوقواق لتقديم ضمانات مساحة مثالية تقريبًا. ^{[ 32 ]}

تعتمد العديد من البدائل لمرشحات بلوم، بما في ذلك مرشحات القسمة ومرشحات الوقواق ، على فكرة تجزئة المفاتيح إلى أرقام عشوائية. $(\log n+\log \epsilon ^{-1})$ تعتمد هذه التقنية، التي قدمها كارتر وآخرون لأول مرة عام 1978 ^{[ 29 ]،} على إمكانية إنشاء بصمات رقمية مكونة من 10 بتات، ثم تخزين هذه البصمات في جدول تجزئة مضغوط. وتستند هذه التقنية إلى حقيقة أن جداول التجزئة المضغوطة يمكن تنفيذها باستخدام عدد بتات تقريبي من البتات. $n\log n$ تستهلك مساحة أقل من نظيراتها غير المضغوطة. وباستخدام جداول التجزئة المختصرة ، يمكن تقليل استخدام المساحة إلى الحد الأدنى. $n\log _{2}(e/\epsilon )+o(n)$ بتات ^{[ 33 ]} مع دعم العمليات ذات الوقت الثابت في مجموعة واسعة من أنظمة المعلمات.

درس بوتز وساندرز وسينجلر (2007) بعض المتغيرات لمرشحات بلوم التي تتميز إما بسرعتها أو باستهلاكها مساحة أقل من مرشحات بلوم التقليدية. وتتلخص الفكرة الأساسية للمتغير السريع في وضع قيم التجزئة k المرتبطة بكل مفتاح في كتلة واحدة أو كتلتين بنفس حجم كتل ذاكرة التخزين المؤقت للمعالج (عادةً 64 بايت). ومن المفترض أن يُحسّن هذا الأداء بتقليل عدد حالات عدم العثور على البيانات في ذاكرة التخزين المؤقت . إلا أن المتغيرات المقترحة تعاني من عيب يتمثل في استهلاكها مساحة أكبر بنسبة 32% تقريبًا من مرشحات بلوم التقليدية.

يعتمد هذا النوع الموفر للمساحة على استخدام دالة تجزئة واحدة تولد لكل مفتاح قيمة في النطاق $\left[0,n/\varepsilon \right]$ أين $\varepsilon$ يمثل معدل النتائج الإيجابية الخاطئة المطلوب. ثم يتم فرز سلسلة القيم وضغطها باستخدام ترميز غولومب (أو أي تقنية ضغط أخرى) لتشغل مساحة قريبة من $n\log _{2}(1/\varepsilon )$ للاستعلام عن مرشح بلوم باستخدام مفتاح معين، يكفي التحقق مما إذا كانت قيمته المقابلة مخزنة في مرشح بلوم. إن فك ضغط مرشح بلوم بالكامل لكل استعلام سيجعل هذه الطريقة غير قابلة للاستخدام تمامًا. للتغلب على هذه المشكلة، يتم تقسيم سلسلة القيم إلى كتل صغيرة متساوية الحجم، تُضغط كل منها على حدة. عند الاستعلام، لا يلزم فك ضغط سوى نصف كتلة في المتوسط. بسبب تكلفة فك الضغط، قد تكون هذه الطريقة أبطأ من مرشحات بلوم التقليدية، ولكن يمكن تعويض ذلك بحساب دالة تجزئة واحدة فقط.

يصف غراف وليمير (2020) نهجًا يُسمى مرشح XOR ، حيث يقومون بتخزين بصمات الأصابع في نوع معين من جداول التجزئة المثالية ، مما ينتج عنه مرشح أكثر كفاءة في استخدام الذاكرة ( $1.23\log _{2}(1/\varepsilon )$ (بتات لكل مفتاح) وأسرع من مرشحات بلوم أو كوكو. (يأتي توفير الوقت من حقيقة أن عملية البحث تتطلب ثلاث عمليات وصول إلى الذاكرة بالضبط، والتي يمكن تنفيذها جميعًا بالتوازي). ومع ذلك، فإن إنشاء المرشح أكثر تعقيدًا من مرشحات بلوم وكوكو، ولا يمكن تعديل المجموعة بعد إنشائها.

الإضافات والتطبيقات

يوجد أكثر من 60 نوعًا مختلفًا من مرشحات بلوم، والعديد من الدراسات الاستقصائية في هذا المجال، وتطور مستمر في التطبيقات (انظر على سبيل المثال، Luo وآخرون ^{[ 34 ]} ). تختلف بعض هذه الأنواع اختلافًا كبيرًا عن المقترح الأصلي لدرجة أنها تُعتبر خروجًا عن بنية البيانات الأصلية وفلسفتها أو تفرعًا منها. ^{[ 34 ]} ولا يزال العمل جاريًا على إيجاد معالجة توحد مرشحات بلوم مع أعمال أخرى في مجال الإسقاطات العشوائية ، والاستشعار المضغوط ، والتجزئة الحساسة للموقع (مع ذلك، انظر Dasgupta وآخرون ^{[ 35 ]} لمحاولة مستوحاة من علم الأعصاب).

تصفية ذاكرة التخزين المؤقت

أدى استخدام مرشح بلوم لمنع تخزين عمليات البحث ذات الزيارة الواحدة في ذاكرة التخزين المؤقت للويب إلى تقليل معدل الكتابة على القرص بنحو النصف، مما قلل الحمل على الأقراص وربما زاد من أداء القرص. ^{[ 13 ]}

تستخدم شبكات توصيل المحتوى ذاكرات تخزين مؤقتة للويب حول العالم لتخزين محتوى الويب وتقديمه للمستخدمين بأداء وموثوقية أعلى. من أهم تطبيقات مرشحات بلوم استخدامها في تحديد عناصر الويب التي يجب تخزينها في هذه الذاكرات بكفاءة. ما يقارب ثلاثة أرباع عناوين URL التي يتم الوصول إليها من ذاكرة التخزين المؤقتة النموذجية هي عناوين "زيارة واحدة" لا يستخدمها المستخدمون إلا مرة واحدة فقط. من الواضح أن تخزين هذه العناوين في ذاكرة التخزين المؤقتة يُعدّ إهدارًا لموارد القرص، لأنها لن تُستخدم مرة أخرى. لمنع تخزين هذه العناوين، يُستخدم مرشح بلوم لتتبع جميع عناوين URL التي يصل إليها المستخدمون. يتم تخزين عنصر الويب مؤقتًا فقط عندما يتم الوصول إليه مرة واحدة على الأقل، أي عند طلبه للمرة الثانية. يقلل استخدام مرشح بلوم بهذه الطريقة بشكل كبير من عبء الكتابة على القرص، لأن معظم عناوين URL التي يتم الوصول إليها مرة واحدة لا تُكتب في ذاكرة التخزين المؤقتة. علاوة على ذلك، فإن تصفية العناصر التي يتم الوصول إليها مرة واحدة توفر مساحة تخزين مؤقتة على القرص، مما يزيد من معدلات الوصول إلى ذاكرة التخزين المؤقت. ^{[ 13 ]}

تجنب النتائج الإيجابية الخاطئة في عالم محدود

وصف كيس وآخرون بنيةً جديدةً لمرشح بلوم تتجنب النتائج الإيجابية الخاطئة، بالإضافة إلى عدم وجود نتائج سلبية خاطئة كما هو معتاد. ^{[ 36 ]} تُطبَّق هذه البنية على مجموعة محدودة تُختار منها عناصر المجموعة. وهي تعتمد على مخطط اختبار المجموعات التوافقية غير التكيفي الموجود مسبقًا من قِبل إبشتاين وجودريتش وهيرشبيرغ. على عكس مرشح بلوم التقليدي، تُحوَّل العناصر إلى مصفوفة بتات باستخدام دوال حتمية وسريعة وسهلة الحساب. يعتمد الحد الأقصى لحجم المجموعة الذي يُجنَّب فيه النتائج الإيجابية الخاطئة تمامًا على حجم المجموعة، ويُتحكَّم فيه بمقدار الذاكرة المُخصَّصة.

بدلاً من ذلك، يمكن إنشاء مرشح بلوم أولي بالطريقة المعتادة، ثم، ضمن نطاق محدود وقابل للحصر، يمكن تحديد جميع النتائج الإيجابية الخاطئة بشكل شامل، ومن ثم إنشاء مرشح بلوم ثانٍ من تلك القائمة؛ وتُعالج النتائج الإيجابية الخاطئة في المرشح الثاني بنفس الطريقة عن طريق إنشاء مرشح ثالث، وهكذا. ولأن النطاق محدود ومجموعة النتائج الإيجابية الخاطئة تتقلص بشكل كبير مع كل خطوة، فإن هذه العملية تُنتج سلسلة متتالية محدودة من مرشحات بلوم التي (ضمن هذا النطاق المغلق والمحدود) ستنتج فقط نتائج إيجابية صحيحة ونتائج سلبية صحيحة. وللتحقق من الانتماء إلى سلسلة المرشحات، يتم الاستعلام من المرشح الأولي، وإذا كانت النتيجة إيجابية، يتم الرجوع إلى المرشح الثاني، وهكذا. يُستخدم هذا البناء في CRLite ، وهي آلية مقترحة لتوزيع حالة إبطال الشهادات لـ Web PKI ، ويتم استغلال شفافية الشهادات لإغلاق مجموعة الشهادات الموجودة. ^{[ 37 ]}

مرشحات عد التوهج

تُتيح مُرشِّحات العدّ إمكانية تنفيذ عملية حذف على مُرشِّح بلوم دون الحاجة إلى إعادة إنشائه من جديد. في مُرشِّح العدّ، يتم توسيع مواضع المصفوفة (المجموعات) من بت واحد إلى عدّاد متعدد البتات. في الواقع، يُمكن اعتبار مُرشِّحات بلوم العادية مُرشِّحات عدّ بحجم مجموعة بت واحد. وقد طُرحت مُرشِّحات العدّ لأول مرة من قِبل فان وآخرون (2000) .

تُوسّع عملية الإضافة لتشمل زيادة قيمة الخانات، وتتحقق عملية البحث من أن كل خانة من الخانات المطلوبة لا تساوي صفرًا. ثم تتضمن عملية الحذف إنقاص قيمة كل خانة من الخانات المعنية.

يُعدّ تجاوز سعة الخزانات مشكلةً، لذا ينبغي أن تكون الخزانات كبيرةً بما يكفي لجعل هذه الحالة نادرة الحدوث. في حال حدوثها، يجب أن تُبقي عمليات الزيادة والنقصان الخزانات مضبوطةً على القيمة القصوى الممكنة للحفاظ على خصائص مرشح بلوم.

يبلغ حجم العدادات عادةً 3 أو 4 بتات. لذا، تستخدم مرشحات بلوم العددية مساحةً أكبر بثلاث إلى أربع مرات من مرشحات بلوم الثابتة. في المقابل، تسمح هياكل البيانات التي وضعها كلٌ من باج، باج، وراو (2005) وفان وآخرون (2014) بالحذف أيضًا، ولكنها تستخدم مساحةً أقل من مرشح بلوم الثابت.

من المشاكل الأخرى المتعلقة بمرشحات العد محدودية قابليتها للتوسع . فنظرًا لعدم إمكانية توسيع جدول مرشح بلوم للعد، يجب معرفة الحد الأقصى لعدد المفاتيح التي يمكن تخزينها في المرشح مسبقًا. وبمجرد تجاوز السعة المصممة للجدول، سيزداد معدل النتائج الإيجابية الخاطئة بسرعة مع إدخال المزيد من المفاتيح.

قدّم بونومي وآخرون (2006) بنية بيانات تعتمد على التجزئة من اليسار (d-left hashing)، وهي مكافئة وظيفيًا لمرشحات بلوم العددية، ولكنها تستخدم نصف المساحة تقريبًا. ولا تُعاني هذه البنية من مشكلة قابلية التوسع، إذ يُمكن إعادة إدخال المفاتيح في جدول تجزئة جديد بحجم مضاعف عند تجاوز السعة المُصممة.

يمكن أيضًا استخدام النسخة الموفرة للمساحة التي وضعها بوتزي وساندرز وسينجلر (2007) لتنفيذ مرشحات العد من خلال دعم عمليات الإدخال والحذف.

قدّم روتنسترايش، كانيزو ، وكيسلاسي (2012) طريقةً عامةً جديدةً تعتمد على الزيادات المتغيرة، تُحسّن بشكلٍ ملحوظٍ احتمالية النتائج الإيجابية الخاطئة في عدّ مرشحات بلوم ومتغيراتها، مع الحفاظ على دعم عمليات الحذف. على عكس عدّ مرشحات بلوم، عند كل عملية إدخال عنصر، تُزاد العدادات المُجزأة بزيادة متغيرة مُجزأة بدلاً من زيادة الوحدة. للاستعلام عن عنصر، تُؤخذ القيم الدقيقة للعدادات في الاعتبار، وليس فقط كونها موجبة. إذا لم يكن مجموع قيمة العداد يُساوي الزيادة المتغيرة المُقابلة للعنصر المطلوب، يُمكن إرجاع إجابة سلبية للاستعلام.

أظهرت دراسة كيم وآخرون (2019) أن نسبة الخطأ الإيجابي لمرشح عد بلوم تتناقص من k=1 إلى نقطة محددة. $k_{opt}$ ، وتزداد من $k_{opt}$ إلى ما لا نهاية موجبة، ويجد $k_{opt}$ كدالة لعتبة العد. ^{[ 38 ]}

التجميع اللامركزي

يمكن تنظيم مرشحات بلوم في هياكل بيانات موزعة لإجراء حسابات لا مركزية بالكامل للوظائف التجميعية . يتيح التجميع اللامركزي إمكانية الوصول إلى القياسات الجماعية محليًا في كل عقدة من الشبكة الموزعة دون الحاجة إلى كيان حسابي مركزي لهذا الغرض. ^{[ 39 ]}

مرشحات بلوم الموزعة

مرشح بلوم أحادي اللقطة موزع للكشف عن العناصر المكررة مع معدل إنذار خاطئ: يتم توزيع 6 عناصر على 3 وحدات معالجة، لكل منها مصفوفة بتات بطول 4. خلال خطوة الاتصال الأولى، تستقبل وحدة المعالجة الأولى (PE 1) قيمة التجزئة '2' مرتين، ثم تعيد إرسالها إما إلى وحدة المعالجة الثانية (PE 2) أو الثالثة (PE 3)، حسب الوحدة التي أرسلتها لاحقًا. تقوم وحدة المعالجة التي تستقبل قيمة التجزئة '2' بالبحث عن العنصر الذي يحمل هذه القيمة، ثم تُعلّمه على أنه عنصر مكرر محتمل.

يمكن تطبيق مرشحات بلوم المتوازية للاستفادة من وحدات المعالجة المتعددة (PEs) الموجودة في الأجهزة المتوازية التي لا تعتمد على مشاركة البيانات . يُعد تنظيم البيانات غير المرتبة ونقلها أحد أبرز التحديات التي تواجه مرشح بلوم المتوازي، حيث تُوزع هذه البيانات عادةً بالتساوي على جميع وحدات المعالجة عند بدء التشغيل أو عند إدخال الدفعات. لترتيب البيانات، يمكن استخدام طريقتين: إما تطبيق مرشح بلوم على جميع البيانات وتخزينها على كل وحدة معالجة، وهو ما يُعرف بمرشح بلوم المتكرر، أو تقسيم مرشح بلوم على جميع البيانات إلى أجزاء متساوية، حيث تُخزن كل وحدة معالجة جزءًا منها. ^{[ 40 ]} في كلتا الطريقتين، يُستخدم مرشح بلوم "اللقطة الواحدة" الذي يحسب قيمة تجزئة واحدة فقط، مما ينتج عنه قلب بت واحد لكل عنصر، وذلك لتقليل حجم البيانات المنقولة.

تبدأ مرشحات بلوم الموزعة بتجزئة جميع العناصر على وحدة المعالجة المحلية الخاصة بها، ثم فرزها محليًا حسب قيم التجزئة. يمكن تنفيذ ذلك في وقت خطي باستخدام خوارزمية فرز الدلو ، كما يتيح اكتشاف التكرارات محليًا. يُستخدم الفرز لتجميع قيم التجزئة مع وحدة المعالجة المخصصة لها كفاصل لإنشاء مرشح بلوم لكل مجموعة. بعد ترميز مرشحات بلوم هذه باستخدام ترميز غولومب، على سبيل المثال ، يُرسل كل مرشح بلوم كحزمة إلى وحدة المعالجة المسؤولة عن قيم التجزئة المُدخلة فيه. وحدة المعالجة p مسؤولة عن جميع قيم التجزئة بين القيم المُدخلة. $p*(s/|{\text{PE}}|)$ و $(p+1)*(s/|{\text{PE}}|)$ حيث يُمثل s الحجم الإجمالي لمرشح بلوم على جميع البيانات. ولأن كل عنصر يُجزأ مرة واحدة فقط، وبالتالي يتم تعيين بت واحد فقط، فإنه للتحقق من إدراج عنصر في مرشح بلوم، يكفي إجراء العملية على وحدة المعالجة المسؤولة عن قيمة تجزئة هذا العنصر. كما يمكن تنفيذ عمليات الإدراج الفردية بكفاءة عالية، إذ يكفي تغيير مرشح بلوم لوحدة معالجة واحدة فقط، مقارنةً بمرشحات بلوم المتكررة حيث يتعين على كل وحدة معالجة تحديث مرشحها. ومن خلال توزيع مرشح بلوم العام على جميع وحدات المعالجة بدلاً من تخزينه بشكل منفصل على كل وحدة، يمكن زيادة حجم مرشح بلوم بشكل كبير، مما يؤدي إلى سعة أكبر ومعدل إنذارات خاطئة أقل. ويمكن استخدام مرشحات بلوم الموزعة لتحسين خوارزميات الكشف عن العناصر المكررة ^{[ 41 ]} عن طريق تصفية العناصر الأكثر "تميزًا". ويمكن حساب هذه العناصر من خلال إرسال قيم تجزئة العناصر فقط، وليس العناصر نفسها التي يكون حجمها أكبر بكثير، وإزالتها من المجموعة، مما يقلل من عبء العمل على خوارزمية الكشف عن العناصر المكررة المستخدمة لاحقًا.

أثناء تبادل قيم التجزئة، تبحث وحدات المعالجة عن البتات المُفعّلة في أكثر من حزمة بيانات مُستلمة، لأن ذلك يعني أن عنصرين لهما نفس قيمة التجزئة، وبالتالي قد يكونان مُكررين. في هذه الحالة، تُرسل رسالة تحتوي على فهرس البت، وهو أيضًا قيمة تجزئة العنصر الذي قد يكون مُكررًا، إلى وحدات المعالجة التي أرسلت حزمة البيانات التي تحتوي على البت المُفعّل. إذا أُرسلت عدة فهارس إلى نفس وحدة المعالجة من مُرسل واحد، فقد يكون من المفيد تشفير هذه الفهارس أيضًا. جميع العناصر التي لم تُرسل قيم تجزئتها مُجددًا مضمونة الآن بأنها ليست مُكررة ولن تُقيّم مرة أخرى. بالنسبة للعناصر المتبقية، يُمكن استخدام خوارزمية إعادة التقسيم ^{[ 42 ]} . أولًا، تُرسل جميع العناصر التي أُرسلت قيم تجزئتها مُجددًا إلى وحدة المعالجة المسؤولة عن قيمة التجزئة الخاصة بها. أي عنصر ونسخته المُكررة مضمونة الآن على نفس وحدة المعالجة. في الخطوة الثانية، يستخدم كل معالج بيانات خوارزمية تسلسلية للكشف عن العناصر المكررة في العناصر المستقبلة، والتي لا تمثل سوى جزء صغير من عدد العناصر الأولية. وبإتاحة نسبة خطأ إيجابي للكشف عن العناصر المكررة، يمكن تقليل حجم البيانات المرسلة بشكل أكبر، حيث لا يتعين على معالجات البيانات إرسال عناصر ذات تجزئات مكررة على الإطلاق، بل يمكن ببساطة وضع علامة على أي عنصر ذي تجزئة مكررة على أنه مكرر. ونتيجة لذلك، فإن نسبة الخطأ الإيجابي للكشف عن العناصر المكررة هي نفسها نسبة الخطأ الإيجابي لمرشح بلوم المستخدم.

يمكن تكرار عملية تصفية العناصر الأكثر تميزًا عدة مرات بتغيير دالة التجزئة في كل خطوة تصفية. في حال استخدام خطوة تصفية واحدة فقط، يجب أن يكون معدل النتائج الإيجابية الخاطئة منخفضًا. أما إذا تكررت خطوة التصفية مرة واحدة، فقد تسمح الخطوة الأولى بمعدل نتائج إيجابية خاطئة أعلى، بينما تسمح الخطوة الثانية بمعدل أعلى ولكنها تعمل على عدد أقل من العناصر نظرًا لإزالة العديد منها بالفعل في الخطوة السابقة. مع أن استخدام أكثر من تكرارين قد يقلل حجم البيانات المرسلة بشكل أكبر إذا كان عدد العناصر المكررة في المجموعة قليلًا، إلا أن الفائدة المرجوة من هذه التعقيدات الإضافية ضئيلة.

تُنظّم مرشحات بلوم المتكررة بياناتها باستخدام خوارزمية مكعب فائق معروفة للتبادل، على سبيل المثال ^{[ 43 ].} أولًا، تحسب كل وحدة معالجة مرشح بلوم على جميع العناصر المحلية وتخزنه. من خلال تكرار حلقة حيث ترسل وحدات المعالجة في كل خطوة (i) مرشح بلوم المحلي الخاص بها على البعد (i) وتدمج مرشح بلوم الذي تستقبله على البعد (i) مع مرشح بلوم المحلي الخاص بها، يصبح من الممكن مضاعفة عدد العناصر التي يحتويها كل مرشح بلوم في كل تكرار. بعد إرسال واستقبال مرشحات بلوم على جميع $\log |{\text{PE}}|$ تحتوي كل وحدة PE على مرشح Bloom العالمي على جميع العناصر.

تكون مرشحات بلوم المتكررة أكثر كفاءة عندما يكون عدد الاستعلامات أكبر بكثير من عدد العناصر التي يحتويها مرشح بلوم، وتكون نقطة التعادل مقارنةً بمرشحات بلوم الموزعة تقريبًا بعد $|{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|$ الوصول، مع $f^{\text{+}}$ كمعدل النتائج الإيجابية الخاطئة لمرشح التوهج.

مزامنة البيانات

يمكن استخدام مرشحات بلوم لتقريب مزامنة البيانات كما في بايرز وآخرون (2004) . ويمكن استخدام مرشحات بلوم العددية لتقريب عدد الاختلافات بين مجموعتين، وقد وُصف هذا النهج في أغاروال وتراختنبرغ (2006) .

مرشحات بلوم لبيانات البث

يمكن تكييف مرشحات بلوم مع سياق البيانات المتدفقة. على سبيل المثال، اقترح دينغ ورفيعي (2006) مرشحات بلوم المستقرة، والتي تتكون من مرشح بلوم للعد حيث يؤدي إدخال عنصر جديد إلى ضبط العدادات المرتبطة به على القيمة $c$ ، ثم يتم إنقاص عدد ثابت $s$ من العدادات بمقدار 1، وبالتالي تحتوي الذاكرة في الغالب على معلومات حول العناصر الحديثة (بشكل بديهي، يمكن للمرء أن يفترض أن عمر العنصر داخل مرشح بلوم مستقر مكون من $N$ عدادًا يبلغ حوالي $c{\tfrac {s}{N}}$ ). ومن الحلول الأخرى مرشح بلوم المُتقادم، الذي يتكون من مرشحين من نوع بلوم، يشغل كل منهما نصف إجمالي الذاكرة المتاحة: فعندما يمتلئ أحد المرشحين، يتم مسح المرشح الثاني، ثم تُضاف العناصر الأحدث إلى هذا المرشح الفارغ حديثًا. ^{[ 44 ]}

ومع ذلك، فقد ثبت ^{[ 45 ]} أنه بغض النظر عن المرشح، بعد $n$ من عمليات الإدخال، فإن مجموع النتائج الإيجابية الخاطئة $FP$ والنتائج السلبية الكاذبة $FN$ الاحتمالات محدودة من الأسفل بـ $FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}$ حيث $L$ هو عدد جميع العناصر الممكنة (حجم الأبجدية)، و $m هو$ حجم الذاكرة (بالبتات)، بافتراض $n>m$ تُظهر هذه النتيجة أنه بالنسبة $لـ L$ كبيرة بما يكفي و $n$ تقترب من اللانهاية، فإن الحد الأدنى يتقارب إلى $FP+FN=1$ وهي العلاقة المميزة للمرشح العشوائي. لذا، بعد عدد كافٍ من عمليات الإدخال، وإذا كانت الأبجدية كبيرة جدًا بحيث لا يمكن تخزينها في الذاكرة (وهو ما يُفترض في سياق المرشحات الاحتمالية)، يستحيل على أي مرشح أن يتفوق على العشوائية. يمكن الاستفادة من هذه النتيجة بتوقع أن يعمل المرشح على نافذة منزلقة فقط بدلًا من التدفق بأكمله. في هذه الحالة، يُستبدل الأس $n$ في الصيغة أعلاه بالأس $w$ ، مما يُعطي صيغة قد تنحرف عن 1، إذا لم يكن $w$ صغيرًا جدًا.

فلاتر بلومير

صمّم شازيل وآخرون (2004) تعميمًا لمرشحات بلوم، حيث ربطوا قيمةً بكل عنصر مُضاف، مُطبّقين بذلك مصفوفة ترابطية . وكما هو الحال مع مرشحات بلوم، تُحقق هذه البنى استهلاكًا منخفضًا للمساحة بفضل قبولها احتمالًا ضئيلًا للنتائج الإيجابية الخاطئة. في حالة "مرشحات بلوم الأكثر دقة"، تُعرَّف النتيجة الإيجابية الخاطئة بأنها إرجاع نتيجة عندما لا يكون المفتاح موجودًا في الخريطة. ولن تُرجع الخريطة أبدًا قيمةً خاطئةً لمفتاح موجود فيها.

المقاربات المدمجة

اقترح بولدي وفيجنا (2005) تعميمًا لمرشحات بلوم قائمًا على الشبكة . يقوم مُقَرِّب مُدمج بربط كل مفتاح بعنصر من عناصر الشبكة (في مرشحات بلوم القياسية، تُستخدم شبكة ثنائية العناصر منطقية). وبدلًا من مصفوفة بتات، يستخدمان مصفوفة من عناصر الشبكة. عند إضافة ارتباط جديد بين مفتاح وعنصر من عناصر الشبكة، يتم حساب القيمة القصوى للمحتويات الحالية لمواقع المصفوفة k المرتبطة بالمفتاح مع عنصر الشبكة. وعند قراءة القيمة المرتبطة بمفتاح، يتم حساب القيمة الدنيا للقيم الموجودة في مواقع المصفوفة k المرتبطة بالمفتاح. تُقارب القيمة الناتجة القيمة الأصلية من الأعلى.

مرشحات بلوم ذات التقسيم المتوازي

استخدم هذا التطبيق مصفوفة منفصلة لكل دالة تجزئة. تسمح هذه الطريقة بإجراء حسابات تجزئة متوازية لكل من عمليات الإدخال والاستعلام. ^{[ 46 ]}

مرشحات بلوم قابلة للتوسيع

اقترح ألميدا وآخرون (2007) صيغةً معدلةً من مرشحات بلوم قادرةً على التكيف ديناميكيًا مع عدد العناصر المخزنة، مع ضمان أدنى احتمال للنتائج الإيجابية الخاطئة. تعتمد هذه التقنية على سلاسل من مرشحات بلوم القياسية ذات سعة متزايدة واحتمالات نتائج إيجابية خاطئة أقل، وذلك لضمان إمكانية تحديد الحد الأقصى لاحتمال النتائج الإيجابية الخاطئة مسبقًا، بغض النظر عن عدد العناصر المراد إدخالها.

مرشحات التوهج المكاني

اقترح بالميري وكالديروني ومايو (2014) مرشحات بلوم المكانية (SBF) في الأصل كبنية بيانات مصممة لتخزين معلومات الموقع ، لا سيما في سياق بروتوكولات التشفير لحماية خصوصية الموقع . ومع ذلك، فإن السمة الرئيسية لمرشحات بلوم المكانية هي قدرتها على تخزين مجموعات متعددة في بنية بيانات واحدة، مما يجعلها مناسبة لعدد من سيناريوهات التطبيق المختلفة. ^{[ 47 ]} يمكن الاستعلام عن انتماء عنصر ما إلى مجموعة محددة، ويعتمد احتمال الخطأ الإيجابي على المجموعة: فالمجموعات الأولى التي تُدخل في المرشح أثناء الإنشاء يكون لها احتمالات خطأ إيجابي أعلى من المجموعات التي تُدخل في النهاية. ^{[ 48 ]} تتيح هذه الخاصية تحديد أولويات المجموعات، حيث يمكن الاحتفاظ بالمجموعات التي تحتوي على عناصر أكثر أهمية.

مرشحات التوهج الطبقي

يتكون مرشح بلوم متعدد الطبقات من عدة طبقات. تتيح هذه المرشحات تتبع عدد مرات إضافة عنصر ما إلى مرشح بلوم من خلال التحقق من عدد الطبقات التي تحتوي على هذا العنصر. في مرشح بلوم متعدد الطبقات، تُرجع عملية التحقق عادةً رقم أعمق طبقة وُجد فيها العنصر. ^{[ 49 ]}

مرشحات التوهج المخفف

مثال على مرشح بلوم المخفف: البحث عن النمط 11010، بدءًا من العقدة n1.

يمكن اعتبار مرشح بلوم المخفف ذو العمق D بمثابة مصفوفة من D مرشحات بلوم عادية. في سياق اكتشاف الخدمات في الشبكة، تخزن كل عقدة مرشحات بلوم عادية ومخففة محليًا. يشير مرشح بلوم العادي أو المحلي إلى الخدمات التي تقدمها العقدة نفسها. يشير المرشح المخفف من المستوى i إلى الخدمات التي يمكن العثور عليها في العقد التي تبعد i قفزة عن العقدة الحالية. يتم إنشاء القيمة i من خلال جمع مرشحات بلوم المحلية للعقد التي تبعد i قفزة عن العقدة الحالية. ^{[ 50 ]}

على سبيل المثال، لنفترض شبكة صغيرة، كما هو موضح في الرسم البياني أدناه. لنفترض أننا نبحث عن خدمة A التي يُجزأ معرّفها إلى البتات 0 و1 و3 (النمط 11010). ولتكن العقدة n1 نقطة البداية. أولًا، نتحقق مما إذا كانت n1 تُقدم الخدمة A من خلال فحص مرشحها المحلي. بما أن الأنماط لا تتطابق، فإننا نفحص مرشح بلوم المُخفف لتحديد العقدة التي يجب أن تكون القفزة التالية. نلاحظ أن n2 لا تُقدم الخدمة A، ولكنها تقع على المسار المؤدي إلى العقد التي تُقدمها. لذا، ننتقل إلى n2 ونُكرر الإجراء نفسه. سرعان ما نجد أن n3 تُقدم الخدمة، وبالتالي تم تحديد الوجهة. ^{[ 51 ]}

باستخدام مرشحات بلوم المخففة المكونة من طبقات متعددة، يمكن اكتشاف الخدمات على مسافة تزيد عن قفزة واحدة مع تجنب تشبع مرشح بلوم عن طريق تخفيف (إزاحة) البتات التي تحددها المصادر الأبعد. ^{[ 50 ]}

البحث عن التركيب الكيميائي

تُستخدم مرشحات بلوم غالبًا للبحث في قواعد بيانات ضخمة للهياكل الكيميائية (انظر التشابه الكيميائي ). في أبسط الحالات، تقتصر العناصر المُضافة إلى المرشح (والتي تُسمى بصمة في هذا المجال) على الأرقام الذرية الموجودة في الجزيء، أو دالة تجزئة تعتمد على الرقم الذري لكل ذرة وعدد ونوع روابطها. هذه الحالة بسيطة للغاية وغير مُجدية. أما المرشحات الأكثر تطورًا، فتُشفّر أيضًا عدد الذرات، وخصائص البنية الفرعية الأكبر مثل مجموعات الكربوكسيل، وخصائص الرسم البياني مثل عدد الحلقات. في بصمات التجزئة، تُستخدم دالة تجزئة تعتمد على خصائص الذرات والروابط لتحويل رسم بياني فرعي إلى بذرة مولد أرقام عشوائية زائفة ، وتُستخدم قيم الإخراج الأولى لضبط البتات في مرشح بلوم.

بدأت البصمات الجزيئية في أواخر الأربعينيات كوسيلة للبحث عن التراكيب الكيميائية باستخدام البطاقات المثقبة. إلا أنه لم يتم تقديم طريقة تعتمد على التجزئة لتوليد البتات إلا في عام 1990 تقريبًا، عندما قدمت شركة "دايلايت لأنظمة المعلومات الكيميائية" (Daylight Chemical Information Systems, Inc.)، بدلاً من استخدام جدول مُعد مسبقًا. وعلى عكس طريقة القاموس، تُمكّن طريقة التجزئة من تخصيص بتات للبنى الفرعية التي لم يسبق رصدها. في أوائل التسعينيات، كان يُنظر إلى مصطلح "البصمة" على أنه مختلف عن "المفاتيح البنيوية"، ولكن المصطلح توسع منذ ذلك الحين ليشمل معظم الخصائص الجزيئية التي يمكن استخدامها لمقارنة التشابه، بما في ذلك المفاتيح البنيوية، وبصمات العد المتفرق، والبصمات ثلاثية الأبعاد. وعلى عكس مرشحات بلوم (Bloom filters)، تسمح طريقة التجزئة في "دايلايت" بأن يكون عدد البتات المخصصة لكل ميزة دالةً لحجم الميزة، ولكن معظم تطبيقات البصمات الشبيهة بـ"دايلايت" تستخدم عددًا ثابتًا من البتات لكل ميزة، مما يجعلها مرشح بلوم. ويمكن استخدام بصمات "دايلايت" الأصلية لأغراض المقارنة والفحص. يمكن استخدام أنواع أخرى كثيرة من بصمات الأصابع، مثل ECFP2 الشائعة، للمقارنة، ولكن ليس للفحص، لأنها تتضمن خصائص بيئية محلية تُؤدي إلى نتائج سلبية خاطئة عند استخدامها كأداة فحص. وحتى لو تم إنشاؤها بنفس الآلية، فإنها لا تُعدّ مرشحات بلوم، لأنها لا تُستخدم للتصفية.

انظر أيضاً

رسم تخطيطي للعد الأدنى - بنية البيانات الاحتمالية في علوم الحاسوب
تجزئة الميزات – تحويل الميزات إلى متجهات باستخدام دالة تجزئة
MinHash – تقنية استخراج البيانات
مرشح القسمة
قائمة التخطي – بنية بيانات احتمالية
مرشحات بلوم في المعلوماتية الحيوية
مرشح الوقواق – بنية بيانات لتحديد عضوية المجموعة التقريبية

مراجع

الاقتباسات

↑ بلوم (1970) .
↑ بونومي وآخرون (2006) .
↑ Dillinger & Manolios (2004a) ; Kirsch & Mitzenmacher (2006) .
^ ميتسنماخر وأوبفال (2005) .
^ بلوستاين والمعزاوي (2002) ، ص 21 – 22
↑ غوبيناثان، كيران؛ سيرجي، إيليا (2020-07-21). "التحقق من اليقين وعدم اليقين في هياكل استعلام العضوية التقريبية". التحقق بمساعدة الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 12225. سبرينغر، تشام. الصفحات 279-303 . doi : 10.1007/978-3-030-53291-8_16 . ISBN 978-3-030-53290-1. PMC 7363400 .
↑ ميتزنماخر وأوبفال (2005) ، ص 109-111، 308.
↑ ميتزنماخر وأوبفال (2005) ، ص 308.
↑ ستاروبينسكي، تراختنبرغ وأغاروال (2003)
↑ جويل وغوبتا (2010)
1 2 سواميداس، إس. جوشوا؛ بالدي، بيير (2007). "التصحيح الرياضي لمقاييس تشابه بصمات الأصابع لتحسين الاسترجاع الكيميائي". مجلة المعلومات الكيميائية والنمذجة . 47 (3): 952-964 . doi : 10.1021/ci600526a . PMID 17444629 .
↑ داسغوبتا، سانجوي؛ شيهان، تيموثي سي؛ ستيفنز، تشارلز إف؛ نافلاخا، ساكيت (18-12-2018). "بنية بيانات عصبية للكشف عن الحالات الجديدة" . وقائع الأكاديمية الوطنية للعلوم . 115 (51): 13093-13098 . Bibcode : 2018PNAS..11513093D . doi : 10.1073/pnas.1814448115 . ISSN 0027-8424 . PMC 6304992. PMID 30509984 .
1 2 3 ماجز وسيتارامان (2015) .
↑ "وحدة مساهمة فهرس بلوم" . Postgresql.org. 2016-04-01. مؤرشف من الأصل في 2018-09-09 . تم الاسترجاع في 2016-06-18 .
↑ Chang et al. (2006) ; Apache Software Foundation (2012) .
↑ ياكونين، أليكس (25 مارس 2010). "مدونة أليكس ياكونين: تطبيق فلتر بلوم رائع" . Blog.alexyakunin.com. مؤرشف من الأصل بتاريخ 27 أكتوبر 2010. تم الاطلاع عليه بتاريخ 31 مايو 2014 .
↑ "المشكلة رقم 10896048: الانتقال من التصفح الآمن باستخدام مرشح بلوم إلى مجموعة البادئات. - مراجعة الكود" . Chromiumcodereview.appspot.com . تاريخ الاسترجاع: 2014-07-03 .
↑ جونز، جيه سي (9 يناير 2020). "تقديم CRLite: جميع عمليات إلغاء البنية التحتية للمفاتيح العامة للويب، مضغوطة" . مدونة موزيلا للأمن . تم الاطلاع عليه بتاريخ 12 يناير 2026 .
↑ جونز، جيه سي (9 يناير 2020). "التصميم الشامل لـ CRLite" . مدونة موزيلا للأمن . تم الاطلاع عليه بتاريخ 12 يناير 2026 .
↑ كولفيل، ستيوارت (24 أغسطس 2020). "تقديم قائمة حظر إضافات قابلة للتوسع" . مدونة مجتمع إضافات موزيلا . تم الاطلاع بتاريخ 12 يناير 2026 .
↑ غودوين، بوب؛ هوبكروفت، مايكل؛ لو، دان؛ كليمر، أليكس؛ كورمي، ميهايلا؛ إلنيكيتي، سامح؛ يوكسيونغ، هي (2017). "BitFunnel: إعادة النظر في التوقيعات للبحث" (ملف PDF) . وقائع المؤتمر الدولي الأربعين لجمعية ACM SIGIR حول البحث والتطوير في استرجاع المعلومات . الصفحات 605-614 . doi : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8. S2CID 20123252 .
↑ ويسلز (2004) .
↑ "فلتر بلوم | مسرد ريفر" . ريفر فاينانشال . تم الاسترجاع في 14 نوفمبر 2020 .
↑ "Plan 9 /sys/man/8/venti" . Plan9.bell-labs.com. مؤرشف من الأصل بتاريخ 28-08-2014 . تم الاطلاع عليه بتاريخ 31-05-2014 .
↑ "التدوير - التحقق الرسمي" .
↑ مولين (1990) .
↑ "ما هي مرشحات بلوم؟" . موقع Medium. 15 يوليو 2015. تاريخ الاسترجاع: 1 نوفمبر 2015 .
↑ "توثيق Grafana Tempo - التخزين المؤقت" . Grafana . تم الاطلاع عليه بتاريخ 16-11-2022 .
1 2 كارتر، لاري؛ فلويد، روبرت؛ جيل، جون؛ ماركوفسكي، جورج؛ ويغمان، مارك (1978). "مختبرات العضوية الدقيقة والتقريبية" . وقائع الندوة السنوية العاشرة لجمعية ACM حول نظرية الحوسبة - STOC '78 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: مطبعة ACM. الصفحات 59-65 . doi : 10.1145/800133.804332 . S2CID 6465743 .
↑ باج، باج وراو (2005) .
↑ بيندر، مايكل أ.؛ فاراش-كولتون، مارتن؛ جونسون، روب؛ كرانر، راسل؛ كوزماول، برادلي س.؛ ميدجيدوفيتش، دزيلا؛ مونتيس، بابلو؛ شيتي، براديب؛ سبيلان، ريتشارد ب.؛ زادوك، إيريز (يوليو 2012). "لا تضرب بقوة" . وقائع مؤسسة VLDB . 5 (11): 1627-1637 . doi : 10.14778/2350229.2350275 . ISSN 2150-8097 . S2CID 47180056 .
إيفن ، تومر؛ إيفن، غاي؛ موريسون، آدم (مارس 2022). "مرشح البادئة" . وقائع مؤسسة VLDB . 15 (7): 1311-1323 . doi : 10.14778/3523210.3523211 . ISSN 2150-8097 .
↑ بيندر، مايكل أ.؛ فاراش-كولتون، مارتن؛ كوزماول، جون؛ كوزماول، ويليام؛ ليو، مينغمو (9 يونيو 2022). "حول المفاضلة المثلى بين الوقت والمساحة لجداول التجزئة" . وقائع الندوة السنوية الرابعة والخمسين لجمعية ACM SIGACT حول نظرية الحوسبة . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 1284-1297 . arXiv : 2111.00602 . doi : 10.1145/3519935.3519969 . hdl : 1721.1/146419 . ISBN 9781450392648. S2CID 240354692 .
1 2 لو، لايلونغ؛ غو، ديك؛ ما، ريتشارد تي بي؛ روتنسترايش، أوري؛ لو، شوشان (13 أبريل 2018). "تحسين مرشح بلوم: التحديات والحلول والمقارنات". arXiv : 1804.04777 [ cs.DS ].
↑ داسغوبتا، سانجوي؛ شيهان، تيموثي سي؛ ستيفنز، تشارلز إف؛ نافلاخاي، ساكيت (2018). "بنية بيانات عصبية للكشف عن الحالات الجديدة" . وقائع الأكاديمية الوطنية للعلوم . 115 (51): 13093-13098 . Bibcode : 2018PNAS..11513093D . doi : 10.1073/pnas.1814448115 . PMC 6304992. PMID 30509984 .
^ قبلة، س.ز. هوسزو، E.؛ تابولكاي، J .؛ رونياي، L.؛ روتنستريتش، أو. (2018). "مرشح بلوم مع منطقة حرة إيجابية كاذبة" (PDF) . وقائع IEEE من INFOCOM . تم الاسترجاع في 4 ديسمبر 2018 .
↑ لاريش، جيمس؛ تشوفنيس، ديفيد؛ ليفين، ديف؛ ماغز، بروس م.؛ ميسلوف، آلان؛ ويلسون، كريستو (2017). "CRLite: نظام قابل للتوسع لإرسال جميع عمليات إلغاء TLS إلى جميع المتصفحات". ندوة IEEE للأمن والخصوصية لعام 2017 (SP) . الصفحات 539-556 . doi : 10.1109/sp.2017.17 . ISBN 978-1-5090-5533-3. S2CID 3926509 .
↑ كيم، كيبوم؛ جيونغ، يونغجو؛ لي، يونغجو؛ لي، سونغجو (11 يوليو 2019). "تحليل مرشحات بلوم للعد المستخدمة في تحديد عتبة العد" . الإلكترونيات . 8 (7): 779. doi : 10.3390/electronics8070779 . ISSN 2079-9292 .
^ بورناراس ووارنير وبرازير (2013) .
↑ ساندرز، بيتر؛ شلاغ، سيباستيان؛ مولر، إنغو (2013). "خوارزميات فعّالة من حيث الاتصال لمشاكل البيانات الضخمة الأساسية". المؤتمر الدولي لهندسة الكهرباء والإلكترونيات (IEEE) حول البيانات الضخمة لعام 2013. الصفحات 15-23 . doi : 10.1109/BigData.2013.6691549 . ISBN 978-1-4799-1293-3. S2CID 15968541 .
↑ شلاغ، سيباستيان (2013). "إزالة التكرارات الموزعة". معهد كارلسروه للتكنولوجيا .
↑ شاتدال، أمبوج؛ جيفري ف. نوتون (1994). "معالجة التجميعات في أنظمة قواعد البيانات المتوازية". قسم علوم الحاسوب، جامعة ويسكونسن-ماديسون : 8.
↑ ف. كومار؛ أ. غراما؛ أ. غوبتا؛ ج. كاريبس (1994). مقدمة في الحوسبة المتوازية. تصميم وتحليل الخوارزميات . بنجامين/كومينغز.
↑ يون، ميونغ كيون (2010). "مرشح بلوم المُعتق مع مخزنين نشطين للمجموعات الديناميكية". معاملات IEEE في هندسة المعرفة والبيانات . 22 (1): 134-138 . Bibcode : 2010ITKDE..22..134Y . doi : 10.1109/TKDE.2009.136 . S2CID 15922054 .
↑ جيرود-ستيوارت، ريمي؛ لومبارد-بلاتيه، ماريوس؛ ناكاش، ديفيد (2020). "الاقتراب من الكشف الأمثل عن التكرارات في نافذة منزلقة". الحوسبة والتوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 12273. الصفحات 64-84 . arXiv : 2005.04740 . doi : 10.1007/978-3-030-58150-3_6 . ISBN 978-3-030-58149-7. S2CID 218581915 .
↑ كيرش، آدم؛ ميتزنماخر†، مايكل. "تقليل التجزئة، نفس الأداء: بناء مرشح بلوم أفضل" (ملف PDF) . كلية هارفارد للهندسة والعلوم التطبيقية . وايلي إنترساينس.
^ كالديروني وبالميري ومايو (2015) .
^ كالديروني وبالميري ومايو (2018) .
^ زيوانج وجونجانج وجيان (2010) .
1 2 كوشيريافي وآخرون. (2009) .
^ كوبياتوفيتش وآخرون. (2000) .

المراجع

أغاروال، ساشين؛ تراختنبرغ، آري (2006). "تقريب عدد الاختلافات بين المجموعات البعيدة". ورشة عمل IEEE لنظرية المعلومات لعام 2006 (ملف PDF) . بونتا دل إيستي، أوروغواي. ص 217. CiteSeerX 10.1.1.69.1033 . doi : 10.1109/ITW.2006.1633815 . ISBN 978-1-4244-0035-5. S2CID 2048278 . {{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
أحمدي، محمود؛ وونغ، ستيفان (2007)، "بنية ذاكرة تخزين مؤقتة لحساب مرشحات بلوم"، المؤتمر الدولي الخامس عشر للشبكات (ICON-2007) ، ص 218، CiteSeerX 10.1.1.125.2470 ، doi : 10.1109/ICON.2007.4444089 ، ISBN 978-1-4244-1229-7، S2CID 2967865
ألميدا، باولو؛ باكيرو، كارلوس؛ بريجويكا، نونو؛ هاتشيسون، ديفيد (2007)، “مرشحات بلوم قابلة للتطوير” (PDF) ، رسائل معالجة المعلومات ، 101 (6): 255–261 ، دوى : 10.1016/j.ipl.2006.10.007 ، hdl : 1822/6627
مؤسسة برمجيات أباتشي (2012)، "11.6. تصميم المخطط" ، دليل مرجع أباتشي إتش بيس، المراجعة 0.94.27
بلوم، بيرتون هـ. (1970)، "المفاضلات بين المساحة والوقت في ترميز التجزئة مع الأخطاء المسموح بها"، اتصالات رابطة مكائن الحوسبة ، 13 (7): 422-426 ، CiteSeerX 10.1.1.641.9096 ، doi : 10.1145/362686.362692 ، S2CID 7931252
بلوستين، جيمس؛ المعزاوي، أمل (2002)، "الحالة المثلى لمرشحات بلوم العامة"، مرشحات بلوم - دليل تعليمي وتحليل ومسح ، كلية علوم الحاسوب بجامعة دالهاوسي، ص 1-31
بولدي، باولو؛ فيجنا، سيباستيانو (2005)، "السلاسل القابلة للتغيير في جافا: التصميم والتنفيذ وخوارزميات البحث النصي الخفيفة" ، مجلة علوم برمجة الحاسوب ، 54 (1): 3-23 ، doi : 10.1016/j.scico.2004.05.003 ، مؤرشف من الأصل في 7 فبراير 2025
بونومي، فلافيو؛ ميتزنماخر، مايكل ؛ بانيغراهي، رينا؛ سينغ، سوشيل؛ فارغيز، جورج (2006)، "بنية محسّنة لحساب مرشحات بلوم"، الخوارزميات - ESA 2006، الندوة الأوروبية السنوية الرابعة عشرة (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب ، المجلد 4168، الصفحات 684-695 ، doi : 10.1007/11841036_61 ، ISBN 978-3-540-38875-3
برودر، أندريه ؛ ميتزنماخر، مايكل (2005)، "تطبيقات مرشحات بلوم على الشبكات: دراسة استقصائية" (ملف PDF) ، رياضيات الإنترنت ، 1 (4): 485-509 ، doi : 10.1080/15427951.2004.10129096 ، S2CID 1560675
بايرز، جون دبليو؛ كونسيدين، جيفري؛ ميتزنماخر، مايكل ؛ روست، ستانيسلاف (2004)، "توصيل المحتوى المُستنير عبر شبكات التراكب التكيفية"، معاملات IEEE/ACM في الشبكات ، 12 (5): 767، Bibcode : 2004ITNet..12..767B ، CiteSeerX 10.1.1.207.1563 ، doi : 10.1109/TNET.2004.836103 ، S2CID 47088273
كالديروني، لوكا؛ بالميري، باولو؛ مايو، داريو (2015)، "خصوصية الموقع بدون ثقة متبادلة: مرشح بلوم المكاني" (ملف PDF) ، اتصالات الحاسوب ، 68 : 4-16 ، doi : 10.1016/j.comcom.2015.06.011 ، hdl : 10468/4762 ، ISSN 0140-3664
كالديروني، لوكا؛ بالميري، باولو؛ مايو، داريو (2018)، "الخصائص الاحتمالية لمرشحات بلوم المكانية وأهميتها لبروتوكولات التشفير"، معاملات IEEE في الطب الشرعي وأمن المعلومات ، 13 (7): 1710-1721 ، Bibcode : 2018ITIF...13.1710C ، doi : 10.1109/TIFS.2018.2799486 ، hdl : 10468/5767 ، ISSN 1556-6013 ، S2CID 3693354
تشانغ، فاي؛ دين، جيفري؛ غيماوات، سانجاي؛ هسيه، ويلسون؛ والاش، ديبورا؛ بوروز، مايك؛ تشاندرا، توشار؛ فايكس، أندرو؛ غروبر، روبرت (2006)، "Bigtable: نظام تخزين موزّع للبيانات المهيكلة"، الندوة السابعة حول تصميم وتنفيذ أنظمة التشغيل
تشارلز، دينيس زافيير؛ تشيلابيلا، كومار (2008)، "مرشحات بلومير: نظرة ثانية"، في هالبرين، دان؛ ميلهورن، كورت (محرران)، الخوارزميات: ESA 2008، الندوة الأوروبية السنوية السادسة عشرة، كارلسروه، ألمانيا، 15-17 سبتمبر 2008، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 5193، سبرينغر، الصفحات 259-270 ، arXiv : 0807.0928 ، doi : 10.1007/978-3-540-87744-8_22 ، ISBN 978-3-540-87743-1، S2CID 643445
شازيل، برنارد ؛ كيليان، جو؛ روبينفيلد، رونيت ؛ تال، أييليت (2004)، "مرشح بلومير: بنية بيانات فعالة لجداول البحث ذات الدعم الثابت"، وقائع الندوة السنوية الخامسة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة (ملف PDF) ، الصفحات 30-39
كوهين، سار؛ ماتياس، يوسي (2003)، "مرشحات التوهج الطيفي"، وقائع مؤتمر ACM SIGMOD الدولي لإدارة البيانات لعام 2003 (ملف PDF) ، الصفحات 241-252 ، doi : 10.1145/872757.872787 ، ISBN 978-1581136340، S2CID 1058187 ، مؤرشف من الأصل (PDF) بتاريخ 10 مارس 2021 ، تم استرجاعه بتاريخ 24 أكتوبر 2019
دينغ، فان؛ رفيعي، داوود (2006)، "الكشف التقريبي عن البيانات المكررة في البيانات المتدفقة باستخدام مرشحات بلوم المستقرة"، وقائع مؤتمر ACM SIGMOD (ملف PDF) ، الصفحات 25-36
دارماپوريكار، سارانج؛ سونغ، هاويو؛ تيرنر، جوناثان؛ لوكوود، جون (2006)، "تصنيف سريع للحزم باستخدام مرشحات بلوم"، وقائع ندوة ACM/IEEE لعام 2006 حول هندسة الشبكات وأنظمة الاتصالات (ملف PDF) ، الصفحات 61-70 ، CiteSeerX 10.1.1.78.9584 ، doi : 10.1145/1185347.1185356 ، ISBN 978-1595935809، S2CID 7848110 ، مؤرشف من الأصل (PDF) بتاريخ 2007-02-02
ديتزفيلبينجر، مارتن؛ باج، راسموس (2008)، "هياكل بيانات موجزة للاسترجاع والعضوية التقريبية"، في أسيتو، لوكا؛ دامغارد، إيفان؛ غولدبيرغ، ليزلي آن؛ هالدورسون، ماغنوس م.؛ إنغولفسدوتير، آنا؛ والوكيفيتش، إيغور (محررون)، الأوتوماتا واللغات والبرمجة: الندوة الدولية الخامسة والثلاثون، ICALP 2008، ريكيافيك، أيسلندا، 7-11 يوليو 2008، وقائع، الجزء الأول، المسار أ: الخوارزميات والأوتوماتا والتعقيد والألعاب ، سلسلة محاضرات في علوم الحاسوب، المجلد. 5125، سبرينغر، الصفحات 385-396 ، arXiv : 0803.3693 ، doi : 10.1007/978-3-540-70575-8_32 ، ISBN 978-3-540-70574-1، S2CID 1699996
ديلينجر، بيتر سي؛ مانوليوس، بانايوتيس (2004أ)، "التحقق السريع والدقيق من حالة البتات لبرنامج SPIN"، وقائع ورشة عمل SPIN الدولية الحادية عشرة حول التحقق من نماذج البرمجيات ، سبرينغر-فيرلاغ، سلسلة محاضرات في علوم الحاسوب 2989
ديلينجر، بيتر سي؛ مانوليوس، بانايوتيس (2004ب)، "مرشحات بلوم في التحقق الاحتمالي"، وقائع المؤتمر الدولي الخامس حول الأساليب الرسمية في التصميم بمساعدة الحاسوب ، سبرينغر-فيرلاغ، سلسلة محاضرات في علوم الحاسوب 3312
دونيه، بينوا؛ باينات، برونو؛ فريدمان، تيمور (2006)، "مرشحات بلوم المُحسّنة: تمكين التطبيقات الشبكية من الموازنة بمرونة بين النتائج الإيجابية الخاطئة والنتائج السلبية الخاطئة"، مؤتمر CoNEXT 06 - المؤتمر الثاني حول تقنيات الشبكات المستقبلية ، مؤرشف من الأصل بتاريخ 17 مايو 2009.
إبستين، ديفيد ؛ وجودريتش، مايكل ت. (2007)، "تحديد البيانات المتأخرة بكفاءة عالية في استخدام المساحة في تدفقات البيانات ذهابًا وإيابًا باستخدام متطابقات نيوتن ومرشحات بلوم القابلة للعكس"، الخوارزميات وهياكل البيانات، ورشة العمل الدولية العاشرة، WADS 2007 ، سلسلة محاضرات في علوم الحاسوب، المجلد 4619، سبرينغر-فيرلاغ، الصفحات 637-648 ، arXiv : 0704.3313 ، Bibcode : 2007arXiv0704.3313E
فان، بن؛ أندرسن، ديف جي؛ كامينسكي، مايكل؛ ميتزنماخر، مايكل دي (2014)، "مرشح الوقواق: أفضل عمليًا من بلوم"، وقائع المؤتمر الدولي العاشر لجمعية آلات الحوسبة حول تجارب وتقنيات الشبكات الناشئة ، الصفحات 75-88 ، doi : 10.1145/2674005.2674994 ، ISBN 9781450332798تطبيق مفتوح المصدر متاح على موقع جيت هاب .
فان، لي؛ كاو، باي ؛ ألميدا، جوسارا ؛ برودر، أندريه (2000)، "ذاكرة التخزين المؤقت الموجزة: بروتوكول قابل للتوسع لمشاركة ذاكرة التخزين المؤقت للويب على نطاق واسع" (ملف PDF) ، معاملات IEEE/ACM في الشبكات ، 8 (3): 281-293 ، رمز Bibcode : 2000ITNet...8..281L ، CiteSeerX 10.1.1.41.1487 ، doi : 10.1109/90.851975 ، S2CID 4779754 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 22-09-2017 ، تم استرجاعه بتاريخ 30-07-2018 ظهرت نسخة أولية في مؤتمر SIGCOMM '98.
جويل، أشيش؛ غوبتا، بانكاج (2010)، "استعلامات المجموعات الفرعية الصغيرة ومرشحات بلوم باستخدام الذاكرة الترابطية الثلاثية، مع تطبيقات" (ملف PDF) ، مجلة ACM SIGMETRICS لتقييم الأداء ، 38 : 143، CiteSeerX 10.1.1.296.6513 ، doi : 10.1145/1811099.1811056
غراف، توماس مولر؛ ليمير، دانيال (2020)، "مرشحات XOR"، مجلة ACM للخوارزميات التجريبية ، 25 : 1-16 ، arXiv : 1912.08258 ، Bibcode : 2019arXiv191208258M ، doi : 10.1145/3376122 ، S2CID 209405019
غراندي، فابيو (2018)، "حول تحليل مرشحات بلوم" (ملف PDF) ، رسائل معالجة المعلومات ، 129 : 35-39 ، doi : 10.1016/j.ipl.2017.09.004
كيرش، آدم؛ ميتزنماخر، مايكل (2006)، "تقليل التجزئة، نفس الأداء: بناء مرشح بلوم أفضل"، في: آزار، يوسي؛ إيرليباخ، توماس (محرران)، الخوارزميات - ESA 2006، الندوة الأوروبية السنوية الرابعة عشرة (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 4168، سبرينغر-فيرلاغ، سلسلة محاضرات في علوم الحاسوب 4168، الصفحات 456-467 ، doi : 10.1007/11841036 ، ISBN 978-3-540-38875-3تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 31 يناير 2009.
كوشيريافي، Y.؛ جيامبين، ج.؛ ستيهل، د.؛ بارسيلو أرويو، ف.؛ براون، T.؛ Siris, V. (2009)، "إدارة حركة المرور وجودة الخدمة في شبكات الوسائط المتعددة اللاسلكية"، التكلفة 290 التقرير النهائي : 111
كوبياتوفيتش، ج.؛ بيندل، د.؛ تشيرفينسكي، ي.؛ جيلز، س.؛ إيتون، د.؛ غومادي، ر.؛ ريا، س.؛ ويذرسبون، هـ.؛ وآخرون (2000)، "أوشن ستور: بنية لتخزين البيانات الدائم على نطاق عالمي" (ملف PDF) ، إشعارات ACM SIGPLAN : 190-201 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 11 مارس 2012 ، تم استرجاعه بتاريخ 1 ديسمبر 2011
ماغز، بروس م .؛ سيتارامان، راميش ك. (يوليو 2015)، "التقنيات الخوارزمية في توصيل المحتوى" (ملف PDF) ، مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب ، 45 (3): 52-66 ، CiteSeerX 10.1.1.696.9236 ، doi : 10.1145/2805789.2805800 ، S2CID 65760 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 14 أغسطس 2021
ميتزنماخر، مايكل ؛ أوبفال، إيلي (2005)، الاحتمالات والحوسبة: الخوارزميات العشوائية والتحليل الاحتمالي ، مطبعة جامعة كامبريدج، الصفحات 107-112 ، ISBN 9780521835404
مورتنسن، كريستيان وورم؛ باج، راسموس ؛ باتراشكو، ميهاي (2005)، "حول الإبلاغ عن النطاق الديناميكي في بُعد واحد"، وقائع الندوة السنوية السابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 104-111 ، arXiv : cs/0502032 ، doi : 10.1145/1060590.1060606 ، ISBN 978-1581139600، S2CID 56473
مولين، جيمس ك. (1990)، "الوصلات الجزئية المثلى لأنظمة قواعد البيانات الموزعة"، معاملات IEEE في هندسة البرمجيات ، 16 (5): 558-560 ، Bibcode : 1990ITSEn..16..558M ، doi : 10.1109/32.52778
باج، آنا؛ باج، راسموس ؛ راو، إس. سرينيفاسا (2005)، "استبدال مرشح بلوم الأمثل"، وقائع الندوة السنوية السادسة عشرة لجمعية آلات الحوسبة والجمعية الدولية للرياضيات التطبيقية حول الخوارزميات المنفصلة ( ملف PDF) ، الصفحات 823-829
بالميري، باولو؛ كالديروني، لوكا؛ مايو، داريو (2014)، "مرشحات بلوم المكانية: تمكين الخصوصية في التطبيقات التي تعتمد على الموقع"، وقائع المؤتمر الدولي العاشر لأمن المعلومات وعلم التشفير (Inscrypt 2014) ، المجلد 8957، سبرينغر-فيرلاغ، سلسلة محاضرات في علوم الحاسوب، الصفحات 16-36 ، CiteSeerX 10.1.1.471.4759 ، doi : 10.1007/978-3-319-16745-9_2 ، ISBN 978-3-319-16744-2
بورات، إيلي (2009)، "استبدال مرشح بلوم الأمثل بناءً على حل المصفوفات"، في فريد، آنا إي؛ موروزوف، أندريه؛ ريبالتشينكو، أندريه؛ فاغنر، كلاوس دبليو (محررون)، علوم الحاسوب، النظرية والتطبيقات: الندوة الدولية الرابعة لعلوم الحاسوب في روسيا، CSR 2009، نوفوسيبيرسك، روسيا، 18-23 أغسطس 2009، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 5675، سبرينغر، الصفحات 263-273 ، arXiv : 0804.1845 ، doi : 10.1007/978-3-642-03351-3_25 ، ISBN 978-3-642-03350-6، S2CID 3205108
بورناراس، إي.؛ وارنييه، إم.؛ برازييه، إف إم تي (2013)، "خدمة تجميع عامة وقابلة للتكيف للشبكات اللامركزية واسعة النطاق"، نمذجة الأنظمة التكيفية المعقدة ، 1 (19): 19، doi : 10.1186/2194-3206-1-19يتوفر نموذج أولي للتطبيق على موقع GitHub .
بوتز، ف.؛ ساندرز، ب .؛ سينجلر، ج. (2007)، "مرشحات بلوم الفعالة من حيث التخزين المؤقت والتجزئة والمساحة"، في ديميتريسكو، كاميل (محرر)، الخوارزميات التجريبية، ورشة العمل الدولية السادسة، WEA 2007 (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 4525، سبرينغر-فيرلاغ، سلسلة محاضرات في علوم الحاسوب 4525، الصفحات 108-121 ، doi : 10.1007/978-3-540-72845-0 ، ISBN 978-3-540-72844-3تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 23 يونيو 2007 ، وتم استرجاعه بتاريخ 18 يوليو 2007.
روتنسترايش، أوري؛ كانيزو، يوسي؛ كيسلاسي، إسحاق (2012)، "مرشح بلوم لعدّ الزيادات المتغيرة"، المؤتمر الدولي السنوي الحادي والثلاثون لجمعية مهندسي الكهرباء والإلكترونيات (IEEE) حول اتصالات الحاسوب، 2012، إنفوكوم 2012 (ملف PDF) ، الصفحات 1880-1888 ، CiteSeerX 10.1.1.174.7165 ، doi : 10.1109/INFCOM.2012.6195563 ، ISBN 978-1-4673-0773-4
سيثومادهافان، سيمها؛ ديسيكان، راجاغوبالان؛ برجر، دوغ؛ مور، تشارلز ر.؛ كيكلر، ستيفن و. (2003)، "إزالة الغموض عن ذاكرة الأجهزة القابلة للتوسع لمعالجات ILP عالية"، المؤتمر الدولي السنوي السادس والثلاثون لـ IEEE/ACM حول الهندسة المعمارية الدقيقة، 2003، MICRO-36 (ملف PDF) ، الصفحات 399-410 ، CiteSeerX 10.1.1.229.1254 ، doi : 10.1109/MICRO.2003.1253244 ، ISBN 978-0-7695-2043-8، S2CID 195881068 ، مؤرشف من الأصل (PDF) بتاريخ 14 يناير 2007
ستاروبينسكي، ديفيد؛ تراختنبرغ، آري؛ أغاروال، ساشين (2003)، "مزامنة فعّالة للأجهزة المساعدة الرقمية الشخصية" (ملف PDF) ، معاملات IEEE في الحوسبة المتنقلة ، 2 (1): 40، رمز Bibcode : 2003ITMC....2...40S ، CiteSeerX 10.1.1.71.7833 ، doi : 10.1109/TMC.2003.1195150
ستيرن، أولريش؛ ديل، ديفيد ل. (1996)، "مخطط جديد للتحقق الاحتمالي الفعال من حيث الذاكرة"، وقائع مؤتمر تقنيات الوصف الرسمي للأنظمة الموزعة وبروتوكولات الاتصال، وتحديد البروتوكول واختباره والتحقق منه: المؤتمر الدولي المشترك IFIP TC6/WG6.1 ، تشابمان وهول، وقائع مؤتمر IFIP، الصفحات 333-348 ، CiteSeerX 10.1.1.47.4101
ويسلز، دوان (يناير 2004)، "10.7 ملخصات الكنوز المخفية"، سكويد: الدليل الشامل ( الطبعة الأولى)، أورايلي ميديا، ص 172، ISBN 978-0-596-00162-9تعتمد ملخصات ذاكرة التخزين المؤقت على تقنية نشرها باي كاو لأول مرة ، وتسمى ذاكرة التخزين المؤقت الموجزة. وتتمثل الفكرة الأساسية في استخدام مرشح بلوم لتمثيل محتويات ذاكرة التخزين المؤقت.
تاركوما، ساسو؛ روثنبرغ، كريستيان إستيف؛ لاغرسبيتز، إيميل (2012)، "نظرية وتطبيق مرشحات بلوم للأنظمة الموزعة"، مجلة IEEE Communications Surveys & Tutorials، العدد 1، المجلد 14، الصفحات 131-155 . (ملف PDF)
تشيوانغ، سين؛ جونغ آنغ، شو؛ جيان، صن (2010)، "مرشح بلوم متعدد الطبقات للكشف عن عناوين URL المكررة"، وقائع المؤتمر الدولي الثالث حول نظرية وهندسة الحاسوب المتقدمة (ICACTE 2010) ، المجلد 1، الصفحات V1–586–V1–591، doi : 10.1109/ICACTE.2010.5578947 ، ISBN 978-1-4244-6539-2، S2CID 3108985

روابط خارجية

شرح مفصل لمرشحات بلوم باستخدام لغة بيرل : "استخدام مرشحات بلوم".
لماذا تعمل مرشحات بلوم بالطريقة التي تعمل بها (مايكل نيلسن، 2012)
مرشحات بلوم - دليل تعليمي وتحليل ودراسة استقصائية (بلوستين والمعزاوي، 2002) في جامعة دالهاوزي
جدول معدلات النتائج الإيجابية الكاذبة لتكوينات مختلفة من موقع جامعة ويسكونسن-ماديسون الإلكتروني
"مرشحات بلوم أكثر فعالية"، إيلي بورات (نوفمبر/2007)، فيديو من سلسلة "حديث تقني" على يوتيوب من جوجل

[FOOTNOTEBloom1970-1] بلوم (1970) .

[FOOTNOTEBonomiMitzenmacherPanigrahySingh2006-2] بونومي وآخرون (2006) .

[3] Dillinger & Manolios (2004a) ; Kirsch & Mitzenmacher (2006) .

[FOOTNOTEMitzenmacherUpfal2005-4] ميتسنماخر وأوبفال (2005) .

[5] بلوستاين والمعزاوي (2002) ، ص 21 – 22

[6] غوبيناثان، كيران؛ سيرجي، إيليا (2020-07-21). "التحقق من اليقين وعدم اليقين في هياكل استعلام العضوية التقريبية". التحقق بمساعدة الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 12225. سبرينغر، تشام. الصفحات 279-303 . doi : 10.1007/978-3-030-53291-8_16 . ISBN 978-3-030-53290-1. PMC 7363400 .

[7] ميتزنماخر وأوبفال (2005) ، ص 109-111، 308.

[8] ميتزنماخر وأوبفال (2005) ، ص 308.

[9] ستاروبينسكي، تراختنبرغ وأغاروال (2003)

[10] جويل وغوبتا (2010)

[Swamidass_2007-11] 1 2 سواميداس، إس. جوشوا؛ بالدي، بيير (2007). "التصحيح الرياضي لمقاييس تشابه بصمات الأصابع لتحسين الاسترجاع الكيميائي". مجلة المعلومات الكيميائية والنمذجة . 47 (3): 952-964 . doi : 10.1021/ci600526a . PMID 17444629 .

[12] داسغوبتا، سانجوي؛ شيهان، تيموثي سي؛ ستيفنز، تشارلز إف؛ نافلاخا، ساكيت (18-12-2018). "بنية بيانات عصبية للكشف عن الحالات الجديدة" . وقائع الأكاديمية الوطنية للعلوم . 115 (51): 13093-13098 . Bibcode : 2018PNAS..11513093D . doi : 10.1073/pnas.1814448115 . ISSN 0027-8424 . PMC 6304992. PMID 30509984 .

[FOOTNOTEMaggsSitaraman2015-13] 1 2 3 ماجز وسيتارامان (2015) .

[14] "وحدة مساهمة فهرس بلوم" . Postgresql.org. 2016-04-01. مؤرشف من الأصل في 2018-09-09 . تم الاسترجاع في 2016-06-18 .

[15] Chang et al. (2006) ; Apache Software Foundation (2012) .

[16] ياكونين، أليكس (25 مارس 2010). "مدونة أليكس ياكونين: تطبيق فلتر بلوم رائع" . Blog.alexyakunin.com. مؤرشف من الأصل بتاريخ 27 أكتوبر 2010. تم الاطلاع عليه بتاريخ 31 مايو 2014 .

[17] "المشكلة رقم 10896048: الانتقال من التصفح الآمن باستخدام مرشح بلوم إلى مجموعة البادئات. - مراجعة الكود" . Chromiumcodereview.appspot.com . تاريخ الاسترجاع: 2014-07-03 .

[18] جونز، جيه سي (9 يناير 2020). "تقديم CRLite: جميع عمليات إلغاء البنية التحتية للمفاتيح العامة للويب، مضغوطة" . مدونة موزيلا للأمن . تم الاطلاع عليه بتاريخ 12 يناير 2026 .

[19] جونز، جيه سي (9 يناير 2020). "التصميم الشامل لـ CRLite" . مدونة موزيلا للأمن . تم الاطلاع عليه بتاريخ 12 يناير 2026 .

[20] كولفيل، ستيوارت (24 أغسطس 2020). "تقديم قائمة حظر إضافات قابلة للتوسع" . مدونة مجتمع إضافات موزيلا . تم الاطلاع بتاريخ 12 يناير 2026 .

[21] غودوين، بوب؛ هوبكروفت، مايكل؛ لو، دان؛ كليمر، أليكس؛ كورمي، ميهايلا؛ إلنيكيتي، سامح؛ يوكسيونغ، هي (2017). "BitFunnel: إعادة النظر في التوقيعات للبحث" (ملف PDF) . وقائع المؤتمر الدولي الأربعين لجمعية ACM SIGIR حول البحث والتطوير في استرجاع المعلومات . الصفحات 605-614 . doi : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8. S2CID 20123252 .

[FOOTNOTEWessels2004-22] ويسلز (2004) .

[23] "فلتر بلوم | مسرد ريفر" . ريفر فاينانشال . تم الاسترجاع في 14 نوفمبر 2020 .

[24] "Plan 9 /sys/man/8/venti" . Plan9.bell-labs.com. مؤرشف من الأصل بتاريخ 28-08-2014 . تم الاطلاع عليه بتاريخ 31-05-2014 .

[25] "التدوير - التحقق الرسمي" .

[FOOTNOTEMullin1990-26] مولين (1990) .

[27] "ما هي مرشحات بلوم؟" . موقع Medium. 15 يوليو 2015. تاريخ الاسترجاع: 1 نوفمبر 2015 .

[28] "توثيق Grafana Tempo - التخزين المؤقت" . Grafana . تم الاطلاع عليه بتاريخ 16-11-2022 .

[:1-29] 1 2 كارتر، لاري؛ فلويد، روبرت؛ جيل، جون؛ ماركوفسكي، جورج؛ ويغمان، مارك (1978). "مختبرات العضوية الدقيقة والتقريبية" . وقائع الندوة السنوية العاشرة لجمعية ACM حول نظرية الحوسبة - STOC '78 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: مطبعة ACM. الصفحات 59-65 . doi : 10.1145/800133.804332 . S2CID 6465743 .

[FOOTNOTEPaghPaghRao2005-30] باج، باج وراو (2005) .

[31] بيندر، مايكل أ.؛ فاراش-كولتون، مارتن؛ جونسون، روب؛ كرانر، راسل؛ كوزماول، برادلي س.؛ ميدجيدوفيتش، دزيلا؛ مونتيس، بابلو؛ شيتي، براديب؛ سبيلان، ريتشارد ب.؛ زادوك، إيريز (يوليو 2012). "لا تضرب بقوة" . وقائع مؤسسة VLDB . 5 (11): 1627-1637 . doi : 10.14778/2350229.2350275 . ISSN 2150-8097 . S2CID 47180056 .

[:0-32] إيفن ، تومر؛ إيفن، غاي؛ موريسون، آدم (مارس 2022). "مرشح البادئة" . وقائع مؤسسة VLDB . 15 (7): 1311-1323 . doi : 10.14778/3523210.3523211 . ISSN 2150-8097 .

[33] بيندر، مايكل أ.؛ فاراش-كولتون، مارتن؛ كوزماول، جون؛ كوزماول، ويليام؛ ليو، مينغمو (9 يونيو 2022). "حول المفاضلة المثلى بين الوقت والمساحة لجداول التجزئة" . وقائع الندوة السنوية الرابعة والخمسين لجمعية ACM SIGACT حول نظرية الحوسبة . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 1284-1297 . arXiv : 2111.00602 . doi : 10.1145/3519935.3519969 . hdl : 1721.1/146419 . ISBN 9781450392648. S2CID 240354692 .

[autogenerated1-34] 1 2 لو، لايلونغ؛ غو، ديك؛ ما، ريتشارد تي بي؛ روتنسترايش، أوري؛ لو، شوشان (13 أبريل 2018). "تحسين مرشح بلوم: التحديات والحلول والمقارنات". arXiv : 1804.04777 [ cs.DS ].

[35] داسغوبتا، سانجوي؛ شيهان، تيموثي سي؛ ستيفنز، تشارلز إف؛ نافلاخاي، ساكيت (2018). "بنية بيانات عصبية للكشف عن الحالات الجديدة" . وقائع الأكاديمية الوطنية للعلوم . 115 (51): 13093-13098 . Bibcode : 2018PNAS..11513093D . doi : 10.1073/pnas.1814448115 . PMC 6304992. PMID 30509984 .

[36] قبلة، س.ز. هوسزو، E.؛ تابولكاي، J .؛ رونياي، L.؛ روتنستريتش، أو. (2018). "مرشح بلوم مع منطقة حرة إيجابية كاذبة" (PDF) . وقائع IEEE من INFOCOM . تم الاسترجاع في 4 ديسمبر 2018 .

[37] لاريش، جيمس؛ تشوفنيس، ديفيد؛ ليفين، ديف؛ ماغز، بروس م.؛ ميسلوف، آلان؛ ويلسون، كريستو (2017). "CRLite: نظام قابل للتوسع لإرسال جميع عمليات إلغاء TLS إلى جميع المتصفحات". ندوة IEEE للأمن والخصوصية لعام 2017 (SP) . الصفحات 539-556 . doi : 10.1109/sp.2017.17 . ISBN 978-1-5090-5533-3. S2CID 3926509 .

[38] كيم، كيبوم؛ جيونغ، يونغجو؛ لي، يونغجو؛ لي، سونغجو (11 يوليو 2019). "تحليل مرشحات بلوم للعد المستخدمة في تحديد عتبة العد" . الإلكترونيات . 8 (7): 779. doi : 10.3390/electronics8070779 . ISSN 2079-9292 .

[FOOTNOTEPournarasWarnierBrazier2013-39] بورناراس ووارنير وبرازير (2013) .

[40] ساندرز، بيتر؛ شلاغ، سيباستيان؛ مولر، إنغو (2013). "خوارزميات فعّالة من حيث الاتصال لمشاكل البيانات الضخمة الأساسية". المؤتمر الدولي لهندسة الكهرباء والإلكترونيات (IEEE) حول البيانات الضخمة لعام 2013. الصفحات 15-23 . doi : 10.1109/BigData.2013.6691549 . ISBN 978-1-4799-1293-3. S2CID 15968541 .

[41] شلاغ، سيباستيان (2013). "إزالة التكرارات الموزعة". معهد كارلسروه للتكنولوجيا .

[42] شاتدال، أمبوج؛ جيفري ف. نوتون (1994). "معالجة التجميعات في أنظمة قواعد البيانات المتوازية". قسم علوم الحاسوب، جامعة ويسكونسن-ماديسون : 8.

[43] ف. كومار؛ أ. غراما؛ أ. غوبتا؛ ج. كاريبس (1994). مقدمة في الحوسبة المتوازية. تصميم وتحليل الخوارزميات . بنجامين/كومينغز.

[AgingBloom-44] يون، ميونغ كيون (2010). "مرشح بلوم المُعتق مع مخزنين نشطين للمجموعات الديناميكية". معاملات IEEE في هندسة المعرفة والبيانات . 22 (1): 134-138 . Bibcode : 2010ITKDE..22..134Y . doi : 10.1109/TKDE.2009.136 . S2CID 15922054 .

[45] جيرود-ستيوارت، ريمي؛ لومبارد-بلاتيه، ماريوس؛ ناكاش، ديفيد (2020). "الاقتراب من الكشف الأمثل عن التكرارات في نافذة منزلقة". الحوسبة والتوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 12273. الصفحات 64-84 . arXiv : 2005.04740 . doi : 10.1007/978-3-030-58150-3_6 . ISBN 978-3-030-58149-7. S2CID 218581915 .

[46] كيرش، آدم؛ ميتزنماخر†، مايكل. "تقليل التجزئة، نفس الأداء: بناء مرشح بلوم أفضل" (ملف PDF) . كلية هارفارد للهندسة والعلوم التطبيقية . وايلي إنترساينس.

[FOOTNOTECalderoniPalmieriMaio2015-47] كالديروني وبالميري ومايو (2015) .

[FOOTNOTECalderoniPalmieriMaio2018-48] كالديروني وبالميري ومايو (2018) .

[FOOTNOTEZhiwangJungangJian2010-49] زيوانج وجونجانج وجيان (2010) .

[FOOTNOTEKoucheryavyGiambeneStaehleBarcelo-Arroyo2009-50] 1 2 كوشيريافي وآخرون. (2009) .

[FOOTNOTEKubiatowiczBindelCzerwinskiGeels2000-51] كوبياتوفيتش وآخرون. (2000) .

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[

[

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

.

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ].

[ 30

[ 31 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ].

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗