A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter). The more elements that are added to the set, the larger the probability of false positives.

Property Value
dbo:abstract
  • A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter). The more elements that are added to the set, the larger the probability of false positives. Bloom proposed the technique for applications where the amount of source data would require an impractically large amount of memory if "conventional" error-free hashing techniques were applied. He gave the example of a hyphenation algorithm for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns. With sufficient core memory, an error-free hash could be used to eliminate all unnecessary disk accesses; on the other hand, with limited core memory, Bloom's technique uses a smaller hash area but still eliminates most unnecessary accesses. For example, a hash area only 15% of the size needed by an ideal error-free hash still eliminates 85% of the disk accesses, an 85–15 form of the Pareto principle. More generally, fewer than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set. (en)
  • 25بك هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (سبتمبر 2016) فلتر بلوم هو هيكل أو بنية بيانات احتمالية موفرة للمساحة. أوجدها بورتون هاوارد بلوم عام 1970وهي تستخدم لاختبار انتماء عنصر لمجموعة من عدمه. يمكن لفلتر بلوم أن يصنف عناصر خطأً على أنها تنتمي لمجموعة، إلا أنه لا تكون إجابته خاطئة أبدا إذا أجاب بعدم وجود العنصر في المجموعة. بمعنى آخر، تجاب الاستعلامات إما بـ"يحتمل أن ينتمي للمجموعة" أو "حتما لا ينتمي للمجموعة". يمكن إضافة عناصر للمجموعة لكن لا يمكن حذفها (لكن هناك حل لذلك مع فلتر "عادّ"). كلما زادت عناصر المجموعة كلما زاد احتمال التصنيفات الإيجابية الخاطئة (إجابة "يحتمل أن ينتمي للمجموعة"). اقترح بلوم هذه الطريقة للتطبيقات التي تستخدم بيانات ضخمة الحجم يصعب معها استخدام تقنيات خوارزميات التجزئة التقليدية. ضرب مثلا بخوارزمية وضع شارطة في الكلمات الإنجليزية لقاموس يحوي نصف مليون كلمة، 90% منها تتبع قواعد شارطة بسيطة، بينما الـ10% المتبقية تحتاج إلى وصول كثيف للقرص الصلب لجلب أنماط وضع شارطة خاصة. إذا توفرت ذاكرة كافية فيمكن استخدام خوارزمية خالية من الإجابات الخاطئة لتفادي الوصول الغير ضروري للقرص. أما إذا كانت الذاكرة محدودة، فطريقة بلوم تستخدم ذاكرة أقل مع تمكنها من استبعاد معظم الوصول الغير ضروري للقرص. على سبيل المثال، مساحة تعادل 15% مما يُستخدم عادة في خوارزميات التجزئة المعتادة الخالية من الإجابات الخاطئة تحول دون 85% من الوصول للقرص، مثلما ينص مبدأ باريتو لكن هذه المرة 85-15. بشكل عام، أقل من 10 بت لكل عنصر مطلوبة لاحتمالات أجوبة خاطئة تبلغ 1%، بغض النظر عن حجم أو عدد العناصر في المجموعة. * 32xبوابة برمجة الحاسوبمشاريع شقيقة في كومنز صور وملفات عن: فلتر بلوم (ar)
  • Ein Bloom-Filter ist eine probabilistische Datenstruktur, mit deren Hilfe sehr schnell festgestellt werden kann, welche Daten in einem Datenstrom schon einmal vorgekommen sind und welche erstmals auftreten. Hierzu wird mit einer geeigneten Zahl von Hash-Funktionen ein „Fingerabdruck“ des gelesenen Datensatzes in einer einzeiligen Hashtabelle hinterlassen. 1970 von Burton H. Bloom zur Rechtschreibkontrolle und zur Worttrennung am Zeilenende entwickelt, werden Bloomfilter heute oft bei der Datenbankverwaltung und für das Routing in Netzwerken eingesetzt. Im Gegensatz zu vergleichbaren Algorithmen brauchen Bloom-Filter nur sehr wenig Speicherplatz. Für die Anwendbarkeit sind aber auch die folgenden Eigenheiten von entscheidender Bedeutung: Schlüsselwerte, die einmal in der Hashtabelle erfasst wurden, verbleiben dort. Weiterhin sind falsch positive Ergebnisse möglich, d.h. was der Filter akzeptiert, war mit hoher Wahrscheinlichkeit in den Schlüsselwerten enthalten; hingegen war definitiv nicht enthalten, was er abweist. (de)
  • Un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation de l'ensemble (comme type abstrait). Cette structure est probabiliste : lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir : * avec certitude que l'élément est absent de l'ensemble (il ne peut pas y avoir de faux négatif) ; * avec une certaine probabilité que l'élément peut être présent dans l'ensemble (il peut y avoir des faux positifs). La taille d'un filtre de Bloom est fixe et indépendante du nombre d'éléments contenus, ce qui est remarquable, et en fait une structure très compacte.L'inconvénient étant qu'il y a d'autant plus de faux positifs qu'il y a d'éléments dans la structure. (fr)
  • Un filtro de Bloom es una estructura de datos probabilística, concebida por Burton Howard Bloom en 1970, que es usada para verificar si un elemento es miembro de un conjunto. Los falsos positivos son posibles pero los falsos negativos no. (es)
  • ブルームフィルタ(Bloom Filter)は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性(False Positive)による誤検出の可能性があるが、偽陰性(False Negative)はない。要素を集合に追加することができるが、削除することはできない(Counting filter を使えば削除できる)。集合に要素が追加されればされるほど、偽陽性の可能性が高くなる。 (ja)
  • 布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。 (zh)
  • Filtr Blooma – tablica bitowa stworzona przez Burtona H. Blooma w 1970 roku. Pierwotnie Filtr Blooma był wykorzystywany do implementacji baz danych, obecnie jest bardzo popularny w sieciach komputerowych. Filtr ten jest strukturą prostą i wydajną pamięciowo, która ma na celu reprezentować zadany zbiór elementów. Zastosowanie znajduje w szybkim określaniu przynależności podanych argumentów do tego zbioru elementów. Filtr Blooma ma jedną wadę. Jego wydajność (oszczędność pamięci) jest możliwa dzięki wprowadzeniu marginesu błędnych pozytywnych odpowiedzi. Efektem tego zabiegu są straty, spowodowane błędnymi informacjami, które często są większe od zaoszczędzonej pamięci. (pl)
  • Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное. Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причём чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). (ru)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 602211 (xsd:integer)
dbo:wikiPageRevisionID
  • 741394302 (xsd:integer)
dct:subject
http://purl.org/linguistics/gold/hypernym
rdf:type
rdfs:comment
  • Un filtro de Bloom es una estructura de datos probabilística, concebida por Burton Howard Bloom en 1970, que es usada para verificar si un elemento es miembro de un conjunto. Los falsos positivos son posibles pero los falsos negativos no. (es)
  • ブルームフィルタ(Bloom Filter)は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性(False Positive)による誤検出の可能性があるが、偽陰性(False Negative)はない。要素を集合に追加することができるが、削除することはできない(Counting filter を使えば削除できる)。集合に要素が追加されればされるほど、偽陽性の可能性が高くなる。 (ja)
  • 布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。 (zh)
  • Filtr Blooma – tablica bitowa stworzona przez Burtona H. Blooma w 1970 roku. Pierwotnie Filtr Blooma był wykorzystywany do implementacji baz danych, obecnie jest bardzo popularny w sieciach komputerowych. Filtr ten jest strukturą prostą i wydajną pamięciowo, która ma na celu reprezentować zadany zbiór elementów. Zastosowanie znajduje w szybkim określaniu przynależności podanych argumentów do tego zbioru elementów. Filtr Blooma ma jedną wadę. Jego wydajność (oszczędność pamięci) jest możliwa dzięki wprowadzeniu marginesu błędnych pozytywnych odpowiedzi. Efektem tego zabiegu są straty, spowodowane błędnymi informacjami, które często są większe od zaoszczędzonej pamięci. (pl)
  • A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter). The more elements that are added to the set, the larger the probability of false positives. (en)
  • 25بك هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (سبتمبر 2016) بشكل عام، أقل من 10 بت لكل عنصر مطلوبة لاحتمالات أجوبة خاطئة تبلغ 1%، بغض النظر عن حجم أو عدد العناصر في المجموعة. * 32xبوابة برمجة الحاسوبمشاريع شقيقة في كومنز صور وملفات عن: فلتر بلوم (ar)
  • Ein Bloom-Filter ist eine probabilistische Datenstruktur, mit deren Hilfe sehr schnell festgestellt werden kann, welche Daten in einem Datenstrom schon einmal vorgekommen sind und welche erstmals auftreten. Hierzu wird mit einer geeigneten Zahl von Hash-Funktionen ein „Fingerabdruck“ des gelesenen Datensatzes in einer einzeiligen Hashtabelle hinterlassen. (de)
  • Un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation de l'ensemble (comme type abstrait). Cette structure est probabiliste : lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir : * avec certitude que l'élément est absent de l'ensemble (il ne peut pas y avoir de faux négatif) ; * avec une certaine probabilité que l'élément peut être présent dans l'ensemble (il peut y avoir des faux positifs). (fr)
  • Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное. (ru)
rdfs:label
  • Bloom filter (en)
  • فلتر بلوم (ar)
  • Bloomfilter (de)
  • Filtro de Bloom (es)
  • Filtre de Bloom (fr)
  • ブルームフィルタ (ja)
  • Filtr Blooma (pl)
  • Фильтр Блума (ru)
  • 布隆过滤器 (zh)
owl:differentFrom
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is foaf:primaryTopic of