Филтър на Блум — вероятностна структура за проверка на членство

Филтър на Блум — компактна вероятностна структура за бърза проверка на членство: ефективно хеширане, значителна икономия на памет и контролирани фалшиво положителни резултати.

Филтърът на Блум е структура от данни, която позволява бързо и пространствено ефективно да се проверява дали даден елемент вероятно принадлежи на множество. Филтрите на Блум използват няколко независими хеш функции и един битов масив (битова таблица). При добавяне на елемент се изчисляват k хеш стойности и съответните позиции в битовия масив се задават на 1. При проверка на принадлежност се изчисляват същите k хеш стойности и ако всички съответни битове са 1, филтърът връща „вероятно в множеството“, иначе „определено не е в множеството“. Това поведение е причината филтърът на Блум да е вероятностна структура от данни: възможни са фалшиво положителни резултати (казва, че е в множеството, когато не е), но не могат да възникнат фалшиво отрицателни (ако филтърът каже, че е извън множеството, е сигурно извън него), при правилно функциониране. Елементите могат да се добавят, но не и стандартно да се премахват; с нарастването на броя добавени елементи вероятността за фалшиво положителен резултат се увеличава.

Произход и мотив

Едуард Блум представя структурата през 1970 г. В своето приложение той разглежда проблем, свързан с автоматичното разделяне на думи в края на реда (хипенизация). В статията той предполага, че съществува алгоритъм за разделяне на думите в края на реда и отбелязва, че повечето думи следват прости модели, но около 10% изискват по-трудни търсения, за да се намери правилното правило. В примера с база от около 500 000 думи традиционните техники за безгрешно хеширане, които съхраняват всички модели, биха изисквали голямо количество памет. Блум показва, че чрез използване на своя подход може да се елиминират повечето скъпи търсения: например хеш-област с размер само 15% от необходимата за идеално безгрешно хеширане все пак премахва около 85% от достъпите до диск.

Как работи (по-подробно)

• Структура: битов масив с дължина m и k независими хеш функции, всяка дава номер на позиция от 0 до m−1.
• Добавяне (insert): за елемент x се изчисляват k хеша h1(x), h2(x), …, hk(x) и битовете в тези позиции се задават на 1.
• Проверка (query): за елемент x се изчисляват същите хешове; ако поне един от съответните битове е 0, елементът определено не е в множеството; ако всички са 1, филтърът връща „вероятно в множеството“ (възможно е фалшиво позитивен отговор).

Вероятности и избор на параметри

Най-често използваните параметри са m (брой битове в масива), n (очакван брой добавени елементи) и k (брой хеш функции). Приблизителната вероятност за фалшиво положителен резултат е

p ≈ (1 − e^(−k n / m))^k

За дадено m и n оптималният брой хеш функции, който минимизира p, е приблизително

k ≈ (m / n) · ln 2

Ако целим определена вероятност p, бита на елемент (m / n) може да се приближително да се изчисли с формула

m / n ≈ −(ln p) / (ln 2)^2

Например, за 1% вероятност за фалшиво положителен резултат са необходими по-малко от 10 бита на елемент (приблизително 9.6 бита), независимо от абсолютния размер на множеството.

Оперативни характеристики

• Време: добавянето и проверката изискват O(k) хеш-изчисления и достъпи до битовия масив. Съвременните реализации използват техники за намаляване на броя на независимите хешове (например двойно хеширане) без да влошават вероятностите.
• Памет: изключително икономична за големи множества, когато се допуска малък процент фалшиви положителни.
• Изтриване: стандартният филтър на Блум не поддържа безопасно изтриване. За да се позволи изтриване, се използва counting Bloom filter — вместо битове се използват броячи (малки цели числа), което увеличава пространствените нужди и въвежда други ограничения.

Разширения и варианти

• Counting Bloom filter — позволява премахване чрез броячи вместо единични битове.
• Scalable Bloom filter — структура, която расте (добавя нови филтри) когато n надвиши първоначалните очаквания, като запазва контрол над общата вероятност за фалшиво положителни.
• Compressed Bloom filter — оптимизации за намаляване на предаването на филтъра през мрежи.
• Други подобрения: разделяне на хешовете, партиционирани филтри, Bloomier filter за асоциативни данни и т.н.

Приложения

Филтрите на Блум се използват широко във виртуална памет, бази данни, системи за кеширане, филтриране на спам, мрежови рутери (за бързи проверки), системи за синхронизация между възли (за намаляване на предаваните данни) и в много други области, където е важна скоростта и икономията на памет при допустимо малък процент фалшиви положителни.

Предимства и недостатъци

• Предимства: много ниска консумация на памет за големи множества, бързи операции, проста структура и лесна имплементация.
• Недостатъци: наличието на фалшиво положителни резултати, невъзможност за стандартно изтриване, чувствителност към точния брой на елементите (n) и избор на параметри m и k.

Практически пример

Ако очакваме n = 1 000 000 елемента и искаме p ≈ 0.01, използваме m/n ≈ 9.6 бита/елемент → m ≈ 9 600 000 бита (~1.2 MB). Оптималното k е около (m / n) ln 2 ≈ 6.7, т.е. 6–7 хеш функции. Това дава добра компромис между памет и вероятност за грешка.

Филтърът на Блум остава популярно и практично решение когато се търси бърза, пространствено ефективна проверка на членство с допускане на малък процент фалшиви положителни отговори.

Въпроси и отговори

В: Какво представлява филтърът на Блум?

Въпрос: Какъв тип структура от данни е филтърът на Блум?

В: Кой предложи филтъра на Блум?

В: Какъв е примерът на Едуард за използване на неговата техника?

В: Колко бита на елемент са необходими за 1% вероятност за фалшиво положителен резултат?

В: Възможно ли е да се премахнат елементи от цветен филтър, след като са добавени?

Въпрос: Добавянето на повече елементи увеличава или намалява вероятността за получаване на фалшиво положителен резултат?

Търсене по буква