| dbo:abstract
|
- فلتر بلوم هو هيكل أو بنية بيانات احتمالية موفرة للمساحة. أوجدها بورتون هاوارد بلوم عام 1970وهي تستخدم لاختبار انتماء عنصر لمجموعة من عدمه. يمكن لفلتر بلوم أن يصنف عناصر خطأً على أنها تنتمي لمجموعة، إلا أنه لا تكون إجابته خاطئة أبدا إذا أجاب بعدم وجود العنصر في المجموعة. بمعنى آخر، تجاب الاستعلامات إما بـ«يحتمل أن ينتمي للمجموعة» أو «حتما لا ينتمي للمجموعة». يمكن إضافة عناصر للمجموعة لكن لا يمكن حذفها (لكن هناك حل لذلك مع فلتر «عادّ»). كلما زادت عناصر المجموعة كلما زاد احتمال التصنيفات الإيجابية الخاطئة (إجابة «يحتمل أن ينتمي للمجموعة»). اقترح بلوم هذه الطريقة للتطبيقات التي تستخدم بيانات ضخمة الحجم يصعب معها استخدام تقنيات خوارزميات التجزئة التقليدية. ضرب مثلا بخوارزمية وضع شارطة في الكلمات الإنجليزية لقاموس يحوي نصف مليون كلمة، 90% منها تتبع قواعد شارطة بسيطة، بينما الـ10% المتبقية تحتاج إلى وصول كثيف للقرص الصلب لجلب أنماط وضع شارطة خاصة. إذا توفرت ذاكرة كافية فيمكن استخدام خوارزمية خالية من الإجابات الخاطئة لتفادي الوصول الغير ضروري للقرص. أما إذا كانت الذاكرة محدودة، فطريقة بلوم تستخدم ذاكرة أقل مع تمكنها من استبعاد معظم الوصول الغير ضروري للقرص. على سبيل المثال، مساحة تعادل 15% مما يُستخدم عادة في خوارزميات التجزئة المعتادة الخالية من الإجابات الخاطئة تحول دون 85% من الوصول للقرص، مثلما ينص مبدأ باريتو لكن هذه المرة 85-15. بشكل عام، أقل من 10 بت لكل عنصر مطلوبة لاحتمالات أجوبة خاطئة تبلغ 1%، بغض النظر عن حجم أو عدد العناصر في المجموعة. (ar)
- Bloomův filtr, pojmenovaný podle , který ho objevil vroce 1970, je prostorověefektivní pravděpodobnostní datová struktura, která se používá na ověřování příslušnostiprvků do množiny. Protože je tato struktura pravděpodobnostní, můžou při tomtoověřování nastat chyby. Při této chybě se o prvku, který ve skutečnosti do dané množiny nepatří, dozvíme,že tam patří, ale nikdy ne naopak. To znamená, že při odpovědi, že daný prvek do množiny nepatří, se dá naBloomův filtr spolehnout na 100%. Pravděpodobnost chyby roste s větším počtem prvků v danémnožině (při pevné velikosti reprezentace). Bloomův filtr se používá v různých aplikacích. Například, databázový systém odspolečnosti Google používá Bloomův filtr na redukování vyhledávání na disku. Před tím, než vůbeczpracuje požadavek, ověří si pomocí Bloomova filtru, zda daný řádek anebo sloupec databázeexistuje (tj. zda patří do množiny reprezentované Bloomovým filtrem). Kvůli charakteru možných chyb připoužití Bloomova filtru se nikdy nemůže stát, že by "přehlédnul" existující záznam. Tím se výrazně zvyšujevýkon databázového systému (při neexistujících záznamech nemusí pokaždé číst z disku) při zachovánístoprocentní spolehlivosti. Bloomovy filtry používá také proxy server Squid pro tzv. cache digests a archivační systém na detekování předtím vloženéhoobsahu. (cs)
- A Bloom filter is a space-efficient probabilistic data structure, conceived by 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 – 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 the variant); the more items added, 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. 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)
- Ein Bloom-Filter (benannt nach ) 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 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 filtro de Bloom es una estructura de datos probabilística, concebida por 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)
- En informatique, et plus précisément en algorithmique, un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation du type abstrait Ensemble. Cette structure est probabiliste, c'est-à-dire qu'elle utilise des probabilités, et que sa correction est probabiliste. Plus précisément, lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir :
* avec certitude l'absence d'un élément (il ne peut pas y avoir de faux négatif) ;
* avec une certaine probabilité la présence d'un élément (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 en fait une structure très compacte. L'inconvénient est toutefois qu'il y a d'autant plus de faux positifs qu'il y a d'éléments dans la structure. Le principe du filtre est le même que pour le hachage. (fr)
- 블룸 필터(Bloom filter)는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조이다. 1970년 Burton Howard Bloom에 의해 고안되었다.블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다. 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다. (ko)
- ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の可能性は増す。 (ja)
- 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)
- 布隆过滤器（英語：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。 (zh)
- Фільтр Блума (англ. Bloom filter) — заощадлива до пам'яті ймовірнісна структура даних, призначена для перевірки приналежності елементів до множини. Запропонована Бартоном Говардом Блумом (англ. Burton Howard Bloom) в 1970 році. Допускає помилкові спрацювання, але пропуск події неможливий, тому фільтр Блума має 100 % потужність. Алгоритм дозволяє перевірити або «ймовірну приналежність до множини», або «точну не приналежність». Можна додавати нові елементи до множини, але не можна їх видаляти (хоча цю проблему можна вирішити «рахуючим» фільтром). Чим більше елементів у множині, тим вища ймовірність помилкового спрацювання. Блум запропонував цей алгоритм для випадків, коли необхідно обробляти таку кількість даних, що звичайні алгоритми хешування потребуватимуть понад міру пам'яті. Як приклад, він навів алгоритм автоматичного перенесення слів зі словником 500 тисяч слів, 90 % яких підпадають під прості правила розбиття, а решта 10 % потребує повільного доступу до жорсткого диску для пошуку конкретних шаблонів розбиття. За умови достатнього обсягу оперативної пам'яті, звичайне хешування позбавило би потреби в зайвих зверненнях до жорсткого диску. Проте, якщо обсяг оперативної пам'яті обмежений, то фільтр Блума дозволяє позбутись більшості зайвих звернень і, при цьому, використовує менше пам'яті. Наприклад, при використанні лише 15 % пам'яті звичайного хеш-алгоритму, фільтр Блума позбувається 85 % запитів до жорсткого диску, що є варіантом 85-15 правила Парето. Зазвичай, незалежно від кількості елементів в множині, достатньо не більше 10 біт на елемент для досягнення частки помилкового спрацювання в 1 %. (uk)
|
| rdfs:comment
|
- Un filtro de Bloom es una estructura de datos probabilística, concebida por 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 Howard Bloom에 의해 고안되었다.블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다. 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다. (ko)
- ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の可能性は増す。 (ja)
- 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年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。 (zh)
- فلتر بلوم هو هيكل أو بنية بيانات احتمالية موفرة للمساحة. أوجدها بورتون هاوارد بلوم عام 1970وهي تستخدم لاختبار انتماء عنصر لمجموعة من عدمه. يمكن لفلتر بلوم أن يصنف عناصر خطأً على أنها تنتمي لمجموعة، إلا أنه لا تكون إجابته خاطئة أبدا إذا أجاب بعدم وجود العنصر في المجموعة. بمعنى آخر، تجاب الاستعلامات إما بـ«يحتمل أن ينتمي للمجموعة» أو «حتما لا ينتمي للمجموعة». يمكن إضافة عناصر للمجموعة لكن لا يمكن حذفها (لكن هناك حل لذلك مع فلتر «عادّ»). كلما زادت عناصر المجموعة كلما زاد احتمال التصنيفات الإيجابية الخاطئة (إجابة «يحتمل أن ينتمي للمجموعة»). (ar)
- Bloomův filtr, pojmenovaný podle , který ho objevil vroce 1970, je prostorověefektivní pravděpodobnostní datová struktura, která se používá na ověřování příslušnostiprvků do množiny. Protože je tato struktura pravděpodobnostní, můžou při tomtoověřování nastat chyby. Při této chybě se o prvku, který ve skutečnosti do dané množiny nepatří, dozvíme,že tam patří, ale nikdy ne naopak. To znamená, že při odpovědi, že daný prvek do množiny nepatří, se dá naBloomův filtr spolehnout na 100%. Pravděpodobnost chyby roste s větším počtem prvků v danémnožině (při pevné velikosti reprezentace). (cs)
- A Bloom filter is a space-efficient probabilistic data structure, conceived by 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 – 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 the variant); the more items added, the larger the probability of false positives. (en)
- Ein Bloom-Filter (benannt nach ) 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)
- En informatique, et plus précisément en algorithmique, un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation du type abstrait Ensemble. Cette structure est probabiliste, c'est-à-dire qu'elle utilise des probabilités, et que sa correction est probabiliste. Plus précisément, lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir : (fr)
- Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая проверять принадлежность элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное. (ru)
- Фільтр Блума (англ. Bloom filter) — заощадлива до пам'яті ймовірнісна структура даних, призначена для перевірки приналежності елементів до множини. Запропонована Бартоном Говардом Блумом (англ. Burton Howard Bloom) в 1970 році. Зазвичай, незалежно від кількості елементів в множині, достатньо не більше 10 біт на елемент для досягнення частки помилкового спрацювання в 1 %. (uk)
|
