Фильтр Блума

редактировать

A Фильтр Блума - это компактная вероятностная структура данных, задуманная в 1970 году, который используется для проверки того, является ли элемент членом набора . Ложноположительные совпадения возможны, но ложноотрицательные - нет - другими словами, запрос возвращает либо «возможно в наборе», либо «определенно не в наборе». Могут быть элементы добавлены в набор, но не удалены (хотя это можно решить с помощью варианта фильтра Блума подсчета); чем больше добавлено элементов, тем больше вероятность ложных срабатываний.

Блум применяемых методов для приложений, в которых объем исходных данных потребовал бы непрактично большой объем памяти, если бы применялись «обычные» безошибочные методы хеширования. Он привел пример алгоритма расстановки переносов для словаря из 500 000 слов, из которых следуют 90% простых правил расстановки переносов, но оставшиеся 10% требуют шаблонов расстановки переносов. При достаточном объеме основной памяти можно использовать безошибочный хэш для устранения всех ненужных обращений к диску; с другой стороны, с ограниченной основной памятью метод Блума использует меньшую хеш-область, но все же устраняет ненужных обращений. Например, хеш-область размером всего 15% от размера, необходимого для идеального безошибочного хеш-кода, по-прежнему устраняет 85% обращений к диску.

В более общем плане для 1% -ного элемента требуется менее 10 битов. вероятность ложного срабатывания, не зависящая от размера или количества элементов в наборе.

Содержание

1 Описание алгоритма
2 Пространственные и временные преимущества
3 Вероятность ложных срабатываний
- 3.1 Оптимальное количество хешей функций
4 Приближение количества элементов в фильтре Блума
- 4.1 Объединение и пересечение множеств
5 Интересные свойства
6 Примеры
7 Альтернативы
8 Расширения и приложения
- 8.1 Фильтрация кэша
- 8.2 Предотвращение ложных срабатываний в конечной вселенной
- 8.3 Подсчет фильтров Блума
- 8.4 Децентрализованное агрегирование
- 8.5 Распределенные фильтры Блума
- 8.6 Синхронизация данных
- 8.7 Фильтры Блумье
- 8.8 Компактные аппроксиматоры
- 8.9 Параллельно-секционные фильтры Блума
- 8.10 Стабильные фильтры Блума
- 8.11 Масштабильные фильтры Блума rs
- 8.12 Фильтры пространственного Блума
- 8.13 Многослойные фильтры Блума
- 8.14 Фильтры ослабленного Блума
- 8.15 Поиск химической структуры
9 См. также
10 Примечания
11 Ссылки
12 Внешние ссылки

Описание алгоритма

Пример фильтра Блума, представляющий набор {x, y, z}. Цветные стрелки показывают в битовом массиве, которому сопоставлен каждый элемент набора. Элемент w не входит в набор {x, y, z}, потому что он хеширует одну позицию этого битового массива, содержащую 0. Для рисунка m = 18 и k = 3.

Пустой фильтр Блума - это битовый массив из m битов, все установлены в 0. Также должно быть определено k различных хэш-функций, каждая из которых отображает или хеширует некоторый набор в один из m позиций массива, генерируя равномерное случайное распределение. Обычно k представляет собой небольшую константу, которая зависит от желаемой частоты ложных ошибок ε, а m пропорциональна k и количеству добавляемых элементов.

Чтобы добавить элемент, передайте его каждую из k хэш-функций, чтобы получить набор элементов. Установите биты во всех этих позициях на 1.

Чтобы запросить элемент (проверить, есть ли он в наборе), передайте его каждую из k хеш-функций, чтобы получить k позиций массива. Если из битов в этих позициях равенство 0, элемент определенно отсутствует в наборе; если бы это было так, тогда все биты были бы установлены в 1, когда он был вставлен. Если все равны 1, то либо элемент находится в наборе, либо биты случайно были установлены в 1 во время вставки других элементов, что приводит к ложному положительному результату. В простом фильтре Блума невозможно различить два случая, но более продвинутые методы могут решить эту проблему.

Требование разработки различных независимых хеш-функций может быть недопустимым для больших k. Для хороших хэш-функций с широким выводом должна быть небольшая корреляция между разными битовыми полями такого хэша, поэтому этот тип хэш-функций можно использовать для генерации нескольких "разных" хэш-функций с помощью разделение его вывода на несколько битовых полей. В качестве альтернативы можно передать k различных начальных значений (например, 0, 1,..., k - 1) хеш-функции, которые принимает начальное значение; или добавьте (или допишите) эти значения к ключу. Независимо от того, что такое ложное срабатывание, может быть ослаблено с помощью большого количества ложных срабатываний. (В частности, Dillinger Manolios (2004b) демонстрирует эффективность использования индексов с использованием или вариантов двойного хеширования, которые фактически являются простыми генераторами случайных чисел, засеянными двумя или двумя хешами значениями..)

Удаление элемента из этого простого фильтра Блума, потому что нет способа сказать, какой из k битов, на который он отображается, следует очистить. Хотя установки любого из этих бит в ноль достаточно для удаления элемента, это также приведет к удалению любых других элементов, которые могут быть на этот бит. Простой алгоритм не дает возможности определить, какие-либо другие элементы, влияющие на биты, для удаляемого элемента.

Единовременное удаление из фильтра Блума можно смоделировать с помощью второго фильтра Блума, который содержит элементы, которые были удалены. Однако ложные срабатывания во втором фильтре становятся ложноотрицательными в составном фильтре, что может быть нежелательно. При таком подходе повторное добавление ранее удаленного элемента невозможно, так как его придется удалить из «удаленного» фильтра.

Часто бывает так, что все ключи доступны, но их перечисление требует больших затрат (например, требует много чтений с диска). Когда количество ложных срабатываний становится слишком высоким, можно регенерировать; это должно быть относительно редким событием.

Преимущества пространства и времени

Фильтр Блума, использование для ускорения ответов в системе хранения ключей и значений. Значения хранятся на диске, который имеет медленное время доступа. Решения по фильтру Блума принимаются намного быстрее. Однако когда фильтр сообщает о положительном результате совершаются ненужные обращения к диску (чтобы отсеять ложные срабатывания). Общая скорость ответа лучше с фильтром Блума, чем без фильтра Блума. Однако использование для этой цели фильтра Увеличение использования памяти.

Несмотря на риск ложных срабатываний, фильтры имеют большое пространственное преимущество перед другими структурами данных для представления наборов, таких как самобалансирующиеся деревья поиска, пробует, хэш-таблицы или простые массивы или связанные списки записей. Большинство из них требует хранения как минимум элементов данных, что может разделять хранилище между элементами с одинаковыми значениями (попытки используются как минимум элементов данных, что может разделять хранилище между элементами с одинаковыми префиксами). Однако фильтры блума вообще не хранят элементы данных, и для фактического хранилища должно быть предусмотрено отдельное решение. Связанные структуры влекут за собой дополнительные линейные накладные расходы на пространство для указателей. Фильтр Блума с ошибкой 1% и оптимальной величиной k, напротив, требует всего 9,6 бит на элемент независимо от размера элементов. Это преимущество частично объясняется его компактностью, унаследованной от массивов, а частично - его вероятностной природой. Частоту ложных срабатываний в 1% можно уменьшить десять раз, добавив всего около 4,8 бит на элемент.

Однако, если количество значений невелико и многие из них могут быть в наборе, фильтр Блума легко превзойти детерминированный битовый массив, требует только один бит для каждого потенциальный элемент. Хеш-таблицы преимущества в отношении и времени, если они начинают игнорировать коллизии и обеспечивают только то, содержит ли каждый сегмент запись; в данном случае они фактически стали фильтрами Блума с k = 1.

Фильтры Блума также обладают необычным своим: время, необходимое либо для добавления элементов, либо для проверки того, находится ли элемент в наборе, является фиксированной константой., O (k), совершенно не зависящее от количества элементов в наборе. Никакая другая структура с постоянным пространством не имеет этого свойства, но среднее время доступа к разреженным хэш-таблицам может сделать их более быстрым, чем некоторые фильтры Блума. Однако в аппаратной реализации Блума эффективен, потому что его запросы независимы и могут быть распараллелены.

Чтобы понять его эффективность использования пространства, поучительно сравнить общий фильтр с его частным случаем, когда k = 1. Если k = 1, то для того, чтобы поддерживать достаточно низкую частоту ложных срабатываний, небольшая доля бит должен быть установлен, что означает, что массив должен быть очень большим и содержать длинные серии нулей. Информационное содержание тип относительно его размера невелико. Обобщенный фильтр Блума (k больше 1) позволяет установить больше битов, сохраняя при этом низкую частоту ложных срабатываний; если параметры (k и m) выбраны правильно, будут установлены примерно половина битов, и они будут явно случайными, они избыточность и минимизируя информационное содержание.

Вероятность ложных срабатываний

Вероятность ложных срабатываний

p {\ displaystyle p}

p

как функция количества элементов

n {\ displaystyle n}

п

в фильтре и размер фильтра

m {\ displaystyle m}

m

. Было принято оптимальное количество хэш-функций

k = (m / n) ln ⁡ 2 {\ displaystyle k = (m / n) \ ln 2}

k = (m / n) \ ln 2

Предположим, что хэш-функция выбирает каждую группу с равной вероятностью. Если m - количество битов в массиве, вероятность того, что данный бит не будет установлен в 1 определенную хеш-функцию во время вставки элемента, составляет

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

1 - {\ гидроразрыв {1} {m}}.

Если k - количество хэш-функций, каждая значимая из них не имеет корреляции между собой, то вероятность, что бит не установлен в 1, любая из хеш-функций равна

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

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

Мы можем использовать известное тождество для e

lim m → ∞ (1-1 м) м = 1 е {\ displaystyle \ lim _ {м \ к \ infty} \ left (1 - {\ frac {1} {m}} \ right) ^ {m} = {\ frac {1} {e}}}

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

для вывода, что для большого m

(1 - 1 m) k = ((1 - 1 m) m) k / m ≈ e - k / m. {\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {k} = \ left (\ left (1 - {\ frac {1} {m}} \ right) ^ {m } \ right) ^ {k / m} \ приблизительно e ^ {- k / m}.}

{\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {k} = \ left (\ left (1 - {\ frac {1} {m}} \ справа) ^ {m} \ right) ^ {k / m} \ приблизительно e ^ {- k / m}.}

Если мы вставили n элементов, вероятность того, что данный бит по-прежнему равен 0, составляет

(1 - 1 м) kn ≈ e - кн / м; {\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {kn} \ приблизительно e ^ {- kn / m};}

{\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {kn} \ приблизительно e ^ {- kn / m};}

вероятность того, что оно равно 1, поэтому

1 - (1 - 1 м) kn ≈ 1 - e - кн / м. {\ displaystyle 1- \ left (1 - {\ frac {1} {m}} \ right) ^ {kn} \ приблизительно 1-e ^ {- kn / m}.}

{\ displaystyle 1- \ left (1 - {\ frac {1} {m}} \ right) ^ {kn } \ примерно 1-е ^ {- кн / м}.}

Теперь проверьте принадлежность элемента этого нет в комплекте. Каждая из k схемы массива, вычисленных хэш-функций, равна 1 с вероятностью, как указано выше. Вероятность того, что все они равны 1, что заставит алгоритм ошибочно утверждено, что элемент находится в наборе, часто задается как

ε = (1 - [1 - 1 m] kn) k ≈ (1 - д - кн / м) к. {\ Displaystyle \ varepsilon = \ left (1- \ left [1 - {\ frac {1} {m}} \ right] ^ {kn} \ right) ^ {k} \ приблизительно \ left (1-e ^ { -kn / m} \ right) ^ {k}.}

{\ displaystyle \ varepsilon = \ left (1- \ left [1 - {\ frac {1} {m}} \ right] ^ {kn} \ right) ^ {k} \ приблизительно \ left (1-e ^ {- kn / m} \ right) ^ {k}.}

Это совсем не правильно, поскольку предполагает независимость вероятностей каждого установленного бита. Однако, предполагая, что это близкое приближение, мы имеем, что вероятность ложных срабатываний уменьшается по мере увеличения m (количества в массиве) и увеличивается по мере увеличения n (количества вставленных элементов).

Альтернативный анализ, приводящий к тому же приближению без предположения о представлении, представлен Митценмахером и Упфалом. После того, как все n элементов были добавлены в фильтр Блума, пусть q будет долей из m битов, которые установлены в 0. (То есть количество битов, все еще элементы в 0, равно qm.) в наборе, для конструкции, заданной любой из k хэш-функций, вероятность того, что бит будет найден установленным в 1, составляет $1 - q {\ displaystyle 1-q}$ $1-q$ . Таким образом, вероятность того, что все k хэш-функций обнаружен, что бит установлен в 1, равна $(1 - q) k {\ displaystyle (1-q) ^ {k}}$ $(1-q) ^ {k}$ . Кроме того ожидаемого значения q - это вероятность того, что данная позиция будет представлена каждой из k хэш-функций для каждого из n элементов, что (как указано выше)

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

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

Без предположения независимости можно доказать, что q очень сконцентрирован вокруг своего ожидаемого значения. В частности, из неравенства Адзумы - Хёффдинга они доказывают, что

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

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

Потому что Исходя из этого, мы можем сказать, что точная вероятность ложных срабатываний составляет

∑ t Pr (q = t) (1 - t) k ≈ (1 - E [q]) k = (1 - [1 - 1 m ] кн) К ≈ (1 - е - кн / м) к {\ displaystyle \ sum _ {t} \ Pr (q = t) (1-t) ^ {k} \ приблизительно (1-E [q]) ^ {k} = \ left (1- \ left [1 - {\ frac {1} {m}} \ right] ^ {kn} \ right) ^ {k} \ приблизительно \ left (1-e ^ {- kn / m} \ right) ^ {k}}

\ sum _ {t} \ Pr (q = t) (1-t) ^ {k} \ приблизительно (1-E [q]) ^ {k} = \ left (1- \ left [1 - {\ frac {1} {m}} \ right] ^ {kn} \ right) ^ {k} \ приблизительно \ left (1-e ^ {- kn / m} \ right) ^ {k}

как и раньше.

Оптимальное количество хэш-функций

Количество хеш-функций k должно быть положительным целым числом. Если оставить это ограничение в стороне, для заданных m и n значение k, которое минимизирует вероятность ложного срабатывания, равно

k = mn ln ⁡ 2. {\ displaystyle k = {\ frac {m} {n}} \ ln 2.}

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

Требуемое количество битов m при заданном n (количестве вставленных элементов) и желаемой вероятности ложного значения срабатывания ε (и при условии, что используется оптимальное значение k) можно вычислить, подставив оптимальное значение k в приведенном выше выражении вероятности:

ε знак равно (1 - е - (мн ln ⁡ 2) нм) мин пер ⁡ 2 {\ displaystyle \ varepsilon = \ left (1-e ^ {- ({\ frac {m} {n}} \ ln 2) { \ frac {n} {m}}} \ right) ^ {{\ frac {m} {n}} \ ln 2}}

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

что может быть упрощено до:

ln ⁡ ε = - mn (ln ⁡ 2) 2. {\ displaystyle \ ln \ varepsilon = - {\ frac {m} {n}} \ left (\ ln 2 \ right) ^ {2}.}

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

Это приводит к:

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

{\ displaystyle m = - {\ frac {п \ пер \ varepsilon} {(\ пер 2) ^ {2}}}}

Таким образом, оптимальное количество битов на элемент

mn = - журнал 2 ⁡ ε ln ⁡ 2 ≈ - 1,44 журнал 2 ⁡ ε {\ displaystyle {\ frac {m} {n}} = - {\ frac {\ log _ {2} \ varepsilon} {\ ln 2}} \ приблизительно -1,4 \ log _ {2} \ varepsilon}

{\ displaystyle {\ frac {m} {n}} = - {\ frac {\ log _ { 2} \ varepsilon} {\ ln 2}} \ приблизительно -1,44 \ log _ {2} \ varepsilon}

с другими хэш-функциями k (без учета целочисленности):

k = - ln ⁡ ε ln ⁡ 2 = - log 2 ⁡ ε. {\ displaystyle k = - {\ frac {\ ln \ varepsilon} {\ ln 2}} = - \ log _ {2} \ varepsilon.}

{\ displaystyle k = - {\ frac {\ ln \ varepsilon} {\ l п 2}} = - \ log _ {2} \ varepsilon.}

Это означает, что для данной вероятности ложного срабатывания ε длина фильтра Блума m пропорционален количеству фильтруемых элементов, необходимое количество хэш-функций зависит только от предполагаемой вероятности ложноположительного результата ε.

Формула $m = - n ln ⁡ ε (ln ⁡ 2) 2 {\ displaystyle m = - {\ frac {n \ ln \ varepsilon} {(\ ln 2) ^ {2}} }}$ ${\ displaystyle m = - {\ frac {п \ пер \ varepsilon} {(\ пер 2) ^ {2}}}}$ приблизительным по трем причинам. Во-первых, и это название опасно, он равен равенству $1-1 м {\ displaystyle 1 - {\ frac {1} {m}}}$ ${\ displaystyle 1 - {\ frac { 1} {m}}}$ как $e - 1 м { \ displaystyle e ^ {- {\ frac {1} {m}}}}$ ${ \ displaystyle е ^ {- {\ гидроразрыва {1} {m}}}}$ , что является хорошим асимптотическим приближением (т.е. справедливым при m → ∞). В-третье, что наиболее важно, определенное, когда один проверяемый бит установлен в 1, не зависит от события, когда любой другой тестируемый бит установлен в 1. В-третьем, что наиболее важно, первое., что $k = mn ln ⁡ 2 {\ displaystyle k = {\ frac {m} {n}} \ ln 2}$ ${\ displaystyle к = {\ гидроразрыва {м} { п}} \ ln 2}$ случайно является целым.

Гоэль и Гупта, однако, дают строгую верхнюю границу, которая не делает никаких предположений. Они показывают, что вероятность ложного срабатывания для конечного фильтра Блума с m битами ( $m>1 {\ displaystyle m>1}$ $m>1$ ), n элементов и k хэш-функций не более

ε ≤ (1 - e - к ( N + 0,5) м - 1) к. {\ Displaystyle \ varepsilon \ leq \ left (1-e ^ {- {\ frac {k (n + 0,5)} {m-1}}} \ right) ^ {k}.}

{\ displaystyle \ varepsilon \ leq \ left (1-е ^ {- {\ гидроразрыва {к (п + 0,5)} {м- 1}}} \ справа) ^ {к}.}

Эту границу можно интерпретировать как указание на то, что приближенная формула $(1 - e - knm) k {\ displaystyle \ left (1-e ^ {- {\ frac {kn } {m}}} \ right) ^ {k}}$ ${\ displaystyle \ left (1-e ^ {- {\ frac {kn} {m}}} \ right) ^ {k}}$ может правил со штрафом не более чем на половину дополнительного элемента и не более чем на один бит меньше.

Приближение количества элементов в Фильтр Блума

Swamidass Baldi (2007) показал, что количество элементов в фильтре Блума может быть аппроксимировано следующей формулой:

n ∗ = - mk ln ⁡ [1 - X m], {\ displaystyl en ^ {*} = - {\ frac {m} {k}} \ ln \ left [1 - {\ frac {X} {m}} \ right],}

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

где $n ∗ {\ displaystyle n ^ {*}}$ $n ^ {*}$ - оценка количества элементов в фильтре, m- длина (размер) фильтра, k- количество хеш-функций, а X- количество битов, созданной в единицу.

Объединение и пересечение наборов

Фильтры Блума - это способ компактного представления элементов набора. Обычно пытаются вычислить размер пересечения или объединения двух наборов. Фильтры Блума можно использовать для приблизительного определения размера пересечения и объединения двух наборов. Swamidass Baldi (2007) показали, что для двух фильтров Блума длины m их количество, соответственно, может быть оценено как

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

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

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

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

Размер их объединения можно оценить как

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

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

где $n (A ∪ B) {\ displaystyle n (A \ cup B)}$ $n (A \ чашка B)$ - количество битов, равное единице в любом двух фильтров Блума. Наконец, пересечение можно оценить как

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

{\ displaystyle n (A ^ {*} \ cap B ^ {*}) = n ( A ^ {*}) + n (B ^ {*}) - n (A ^ {*} \ чашка B ^ {*}),}

используя три формулы вместе.

Интересные свойства

В отличие от стандартной хэш-таблицы, использующей открытую адресацию для разрешения конфликтов, фильтр Блума фиксированного размера может представлять набор с сколь угодно большим количеством элементов; добавление элемента никогда не заканчивается неудачей из-за «заполнения» структуры данных. Однако частота ложных срабатываний постоянно увеличивается по мере добавления элементов, пока все биты в фильтре не будут установлены в 1, после чего все запросы будут давать положительный результат. При открытом хешировании адресации ложные срабатывания никогда не возникают, но производительность постоянно ухудшается, покане приближается к линейному поиску.
Объединение и пересечение фильтров Блума с одинаковым размером и набором хэш-функций может быть реализовано с помощью побитовых операций ИЛИ и И соответственно. Операция объединения фильтров Блума не имеет потерь в том смысле, что результирующий фильтр Блума совпадает с фильтром Блума, созданным с нуля с использованием двух наборов. Операция пересечения удовлетворяет более слабому свойству: вероятность ложного срабатывания в результирующем фильтре Блума не больше вероятности ложного срабатывания в одном из составляющих фильтров, но может быть больше, чем вероятность ложного срабатывания в фильтре Блума, созданного с использованием нуля с использованием двух наборов.
Некоторые виды наложенного кода можно рассматривать как фильтр Блума, реализованный с помощью физических карточек с надрезом. Примером может быть Затокодирование, изобретенное Кэлвином Мурсом в 1947 году, в котором представлен набор категорий, связанных с частью информации, представлен в виде меток на карточке со случайным лоном из четырех выемки для каждой категории.

Примеры

Плодовые мушки использовать модифицированную версию фильтров для обнаружения новизны запаха с дополнительными функциями, включая сходство нового запаха с запахом ранее испытанных примеров, и время, прошедшее с момента предыдущего ощущения того же запаха.
Серверы Akamai Technologies, провайдера доставки контента, используют фильтры Блума, чтобы предотвратить сохранение "одноразовых чудес" в его дисковых кешах. Одноразовые чудеса - это веб-объекты, запрашиваемые пользователями только один раз, как обнаружил Akamai, применимо почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса веб-объекта и кэширования этого объекта только при его втором запросе предотвращает попадание «чудес с одним попаданием» в дисковый кеш, что снижает нагрузку на диск и увеличивает процент попаданий в дисковый кеш.
Google Bigtable, Apache HBase и Apache Cassandra и PostgreSQL используют фильтры Блума, чтобы уменьшить количество запросов на диск для несуществующих строк или столбцов. Избежание дорогостоящих поисков на диске увеличивает результаты операции запроса к базе данных.

Google Chrome

Microsoft Bing (использует поисковую систему) многоуровневые иерархические фильтры Блума для своего поискового индекса BitFunnel. Фильтры Блума обеспечли более низкую стоимость, чем предыдущий индекс Bing, который был основан на инвертированных файлах.
Squid Веб Прокси Кэш использует фильтры Блума для дайджесты кеша.
использует Биткойн фильтры Блума для ускорения синхронизации кошелька.
Система архивного хранения Venti использует фильтры Блума для обнаружения ранее сохраненных данных.
Средство проверки модели SPIN использует фильтры Блума для достижения достижимого пространства состояний для больших проблем проверки.
Аналитическая структура использует Каскадная фильтры Блума для ускорения асимметричной объединяется, когда один из объединенных наборов данных значительно больше, чем другой (в литературе по базам данных часто называется объединением Блума).
Exim агент передачи почты (MTA) использует фильтры Блума в его функции ограничения скорости.
Средний использует фильтры Блума, чтобы не рекомендовать статьи, которые пользователь ранее читал.
Ethereum использует Блума для быстрого поиска журналов в блоке Ethereum ckchain.

Альтернативы

Классические фильтры Блума используют $1,44 log 2 ⁡ (1 / ε) {\ displaystyle 1.44 \ log _ {2} (1 / \ varepsilon)}$ ${\ displaystyle 1.44 \ log _ {2} (1 / \ varepsilon)}$ бит пространства на вставленный ключ, где $ε {\ displaystyle \ varepsilon}$ $\ varepsilon$ - частота ложных срабатываний фильтра Блума. Пространство, которое строго необходимо для любой структуры данных, играющей ту же роль, что и фильтр Блума, составляет всего $log 2 ⁡ (1 / ε) {\ displaystyle \ log _ {2} (1 / \ varepsilon)}$ ${\ displaystyle \ log _ {2} ( 1 / \ varepsilon)}$ на разреш. Следовательно, фильтры Блума используют на 44% больше места, чем эквивалентная оптимальная структура данных. Вместо этого Pagh et al. обеспечить оптимальную структуру данных. Более того, их структура данных имеет постоянную локальность ссылок независимо от частоты ложных срабатываний, в отличие от фильтров Блума, где более низкая частота ложных срабатываний $ε {\ displaystyle \ varepsilon}$ $\ varepsilon$ приводит к большему количеству обращений к памяти на запрос, $log ⁡ (1 / ε) {\ displaystyle \ log (1 / \ varepsilon)}$ ${\ displaystyle \ log (1 / \ varepsilon)}$ . Кроме того, он позволяет удалять элементы без штрафа за место, в отличие от фильтров Блума. Те же улучшенные оптимального использования пространства, постоянной локальности ссылки и возможности удаления элементов также обеспечиваются фильтром кукушка из Fan et al. (2014), реализация доступна с открытым исходным кодом.

Стерн и Дилл (1996) описывают вероятностную структуру, основанную на хэш-таблицах, которые Диллинджер и Манолиос (2004b) определяют как более точные, чем фильтр Блума, когда каждый настроен оптимально. Диллинджер и Манолиос, однако, отмечают, что разумная точность любого фильтра Блума в широком диапазоне количества добавлений делает его привлекательным для вероятностного перечисления пространств состояния неизвестного размера. Таким образом, сжатие хэша является привлекательным, когда количество добавлений можно точно спрогнозировать; Однако, несмотря на то, что это очень быстрое программное обеспечение, сжатие хэшей плохо подходит для оборудования из-за наихудшего линейного времени доступа.

Putze, Sanders Singler (2007) изучили некоторые варианты фильтров Блума, которые либо быстрее, либо занимают меньше места, чем классические фильтры Блума. Основная идея быстрого варианта состоит в том, чтобы включить один из значений хэша, в каждом из которых указан тот же размер, что и блоки кэша памяти процессора (обычно 64 байта). Это, по-видимому, улучшит производительность за счет уменьшения количества промахов кэша памяти. Однако предлагаемые варианты имеют недостаток в том, что они используют примерно на 32% больше места, чем классические фильтры Блума.

Вариант с использованием используемого пространства на базе одной хеш-функции, который генерирует для каждого значения в диапазоне $[0, n / ε] {\ displaystyle \ left [0, n / \ varepsilon \ \ right]}$ $\ left [0, n / \ varepsilon \ right]$ где $ε {\ displaystyle \ varepsilon}$ $\ varepsilon$ - запрошенная частота ложных срабатываний. Последовательность значений сортируется и сжимается с использованием кодирования Голомба (или какой-либо другой техники сжатия), чтобы занять пространство, близкое к $n log 2 ⁡ (1 / ε) {\ displaystyle n \ log _ {2} (1 / \ varepsilon)}$ ${\ displaystyle n \ log _ {2} (1 / \ varepsilon)}$ бит. Чтобы запросить фильтр Блума для данного ключа, проверить, сохранено ли его соответствующее значение в фильтре Блума. Распаковка всего фильтра этот вариант полностью непригодным для использования. Чтобы решить эту проблему, последовательность разделяется на небольшие блоки равного размера, которые сжимаются отдельно. Во время запроса в среднем нужно будет распаковать только половину блока. Из-за накладных расходов на декомпрессию этот вариант может быть медленнее, чем классические фильтры блума, но это может быть компенсировано тем фактом, что необходимо вычислить одну хэш-функцию.

Другой альтернативный классический фильтру Блума является фильтром с кукушкой, основанным на компактных вариантах хеширования с кукушкой. В этом случае создается хэш-таблица, не содержится ни ключей, ни значений, коротких отпечатков (небольших хешей) ключей. Если поиск ключа обнаруживает соответствующий отпечаток пальца, вероятно, находится ключ в наборе. Одно из полезных свойств фильтров с кукушкой состоит в том, что их можно обновлять; записи могут быть добавлены динамически (с небольшой вероятностью сбоя из-за переполнения хеш-таблицы) и удалены.

Graf Lemire (2019) представленный подход, называемый фильтром xor, где они хранят отпечатки пальцев в конкретном типе таблицы точного хэша, создавая фильтр, который более эффективен с точки памяти ( $1,23 log 2 ⁡ (1 / ε) {\ displaystyle 1.23 \ log _ {2} (1 / \ varepsilon)}$ ${\ displaystyle 1.23 \ log _ {2} (1 / \ varepsilon)}$ бит на ключ) и быстрее, чем фильтры Блума или кукушки. (Экономия времени достигается за счет того, что для поиска требуется набор потоков доступа к памяти, которые производятся.) Создание фильтра более сложное, чем фильтры Блума и кукушки, и невозможно изменить набор после создания.

Расширения и приложения

Существует более 60 вариантов фильтров Блума, множество обзоров в данной области и постоянный отток приложений (см. Например, Луо и др.). Некоторые из вариантов в структуре отличаются от исходного предложения, чтобы быть нарушением исходной структуры данных и ее философии. Обработка, которая объединяет фильтры Блума с другими работами по случайным проекциям, компрессионному считыванию и хеширование с учетом местоположения, еще предстоит сделать (хотя см. Dasgupta, et al.. одна попытка, вдохновленная нейробиологией).

Фильтрация кэша

Использование фильтра Блума для сохранения в веб-кеше одноразовых чудес уменьшило скорость записи на диск почти вдвое, уменьшив нагрузку на диски и увеличив диск

Сети доставки контента развертывают веб-кеши по всему миру для кэширования и предоставления веб-пользователей пользователям с большей производительностью и надежностью. Ключевым применением фильтров является их использование для эффективного определения веб-кэшах. Почти три четверти URL-адресов, к которым осуществляется доступ из типичного веб-кеша, предоставляет собой «чудеса одного обращения», к которым пользователи обращаются только один раз и никогда больше. Совершенно очевидно, что дисковые ресурсы хранить в веб-кеше одноразовые чудеса расточительно, поскольку к ним больше никогда не будет доступа. Чтобы предотвратить кеширование «чудеса одного удара», используется фильтр Блума для всех URL-адресов, к которым обращаются пользователи. Веб-объект кэшируется только в том случае, если к нему обратились по крайней мере один раз, то есть объект кэшируется по его второму запросу. Использование фильтра таким образом снижает нагрузку на запись на диск, поскольку «чудеса с одним щелчком» никогда не записываются в кэш диска. Кроме того, фильтрация однодневных чудес также экономит место в кэше на диске, увеличивая частоту попаданий в кэш.

Избегание ложных срабатываний в конечной вселенной

Кисс и др. Описали новую конструкцию для фильтра Блума, который позволяет избежать ложных срабатываний в дополнение к типичному отсутствию ложноотрицательных результатов. Конструкция применима к конечной вселенной, из взятой элементов множества. Он основан на существующей схеме неадаптивного комбинаторного группового тестирования Эппштейна, Гудрича и Хиршберга. В отличие от типового фильтра Блума, элементы хешируются в битовый массив с помощью детерминированных, быстрых и простых для вычислений функций. Максимальный размер набора, который при полностью исключаются ложные срабатывания, зависит от размера юниверса и контролируется объемом выделенной памяти.

Подсчет фильтров Блума

Подсчетные фильтры позволяют реализовать удаление для фильтра Блума без повторного создания фильтра. В счетном фильтре конфигурации (сегменты) расширяются от одного бита до многобитового счетчика. Фактически, обычные фильтры Блума можно рассматривать как счетные фильтры с размером корзины в один бит. Счетные фильтры были введены Fan et al. (2000).

Операция вставки расширена для увеличения значения сегментов, а операция поиска проверяет, что каждый из требуемых сегментов не равен нулю. Затем операция удаления состоит из уменьшения значения каждого из соответствующих сегментов.

Арифметическое переполнение сегментов является проблемой, и сегменты должны быть достаточно большими, чтобы сделать этот случай редким. Если это происходит, то операции увеличения и уменьшения должны оставлять для корзины максимально возможное значение, чтобы сохранить свойства фильтра Блума.

Размер счетчиков обычно составляет 3 или 4 бита. Следовательно, подсчетные фильтры Блума занимают в 3-4 раза больше места, чем статические фильтры Блума. Напротив, структуры данных Pagh, Pagh Rao (2005) и Fan et al. (2014) также разрешает удаление, но занимает меньше места, чем статический фильтр Блума.

Другая проблема с подсчетом фильтров - ограниченная масштабируемость. Поскольку счетная таблица фильтра Блума не может быть расширена, максимальное количество ключей, которые будут одновременно храниться в фильтре, должно быть известно заранее. Как только проектная емкость таблицы будет превышена, количество ложных срабатываний будет быстро расти по мере того, как будут вставлены новые ключи.

Бономи и др. (2006) представил структуру данных, основанную на хешировании d-left, которая функционально эквивалентна, но использует примерно половину места, чем подсчет фильтров Блума. Проблема масштабируемости не возникает в этой структуре данных. Как только проектная емкость будет превышена, ключи можно будет повторно вставить в новую хэш-таблицу двойного размера.

Экономичный вариант от Putze, Sanders Singler (2007) также может быть использован для реализации фильтров подсчета с помощью поддержки вставок и удалений.

Rottenstreich, Kanizo Keslassy (2012) представили новый общий метод, основанный на переменном приращении, который увеличивает вероятность ложноположительных результатов подсчета фильтров и их вариантов, при этом поддерживая удаление. В отличие от подсчета фильтров Блума, при каждой вставке элемента хешированные счетчики увеличиваются на приращение хешированной переменной вместо единичного приращения. Чтобы запросить элемент, учитываются точные значения счетчиков, а не только их положительность. Сумма, представленная значением счетчика, не может быть возвращена из соответствующего запрошенного элемента, на запрос может быть возвращен отрицательный ответ.

Ким и др. (2019) показывает, что количество ложных срабатываний фильтра Подсчета Блума уменьшается с k = 1 до точки, определенная $копт {\ displaystyle k_ {opt}}$ ${\ displaystyle k_ {opt}}$ , и увеличивается с $копт {\ displaystyle k_ {opt}}$ ${\ displaystyle k_ {opt}}$ до положительной бесконечности и находит $kopt {\ displaystyle k_ {opt}}$ ${\ displaystyle k_ {opt}}$ как функцию порога подсчета.

Децентрализованное агрегирование

фильтры Блума могут быть организованы в распределенные структуры данных для выполнения полностью децентрализованных вычислений агрегатных функций. Децентрализованная агрегация делает коллективные измерения доступными локально в каждом узле распределенной сети без привлечения для этой цели централизованного вычислительного объекта.

Распределенные фильтры Блума

Распределенный фильтр Блума с единичным запуском для обнаружения дублирования с определением ложных срабатываний: 6 элементов распределяются по 3 PE, каждый из которых имеет битовый массив длиной 4. На первом этапе связи PE 1 дважды получает хэш «2» и отправляет его обратно в PE 2 или 3, в зависимости от того, кто отправил его позже. PE, который получает хэш '2', затем ищет элемент с этим хешем и помечает его как возможный дубликат.

Могут быть реализованы параллельные фильтры для использования нескольких элементов обработки (PE) присутствует в параллельных машинах без совместного использования ресурсов. Одним из основных препятствий для параллельного фильтра является организация и передача неупорядоченных данных, которые, как правило, равномерно распределяются по всем PE при инициации или при пакетной вставке. Чтобы упорядочить данные, можно использовать два подхода: либо фильтр Блума по всем данным, хранящимся на каждом PE, называемый реплицирующим фильтром Блума, либо фильтр по всем данным, разделенным на равные части, причем каждый PE хранилище часть.. Для обоих подходов используется фильтр Блума «Single Shot», который вычисляет только один хэш, в результате чего на каждый элемент приходится один перевернутый бит, чтобы уменьшить объем связи.

Распределенные фильтры Блума запускаются первым хеш-размещением всех элементов на их локальном PE и последующая локальная сортировка их по хешам. Это можно сделать за линейное время, используя, например, Сортировка по сегменту, а также позволяет обнаруживать локальные дубликаты. Сортировка используется для группировки хэшей с назначенным им PE в качестве разделителя для создания фильтра Блума для каждой группы. После кодирования этих фильтров Блума с использованием, например, Кодирование Голомба каждый фильтр Блума отправляется в виде пакета PE, ответственного за хеш-значения, которые были вставлены в него. PE p отвечает за все хэши между значениями $p ∗ (s / | PE |) {\ displaystyle p * (s / | {\ text {PE}} |)}$ ${\ displaystyle p * (s / | {\ text {PE}} |)}$ и $( p + 1) ∗ (s / | PE |) {\ displaystyle (p + 1) * (s / | {\ text {PE}} |)}$ ${\ displaystyle (p + 1) * (s / | {\ text { PE}} |)}$ , где s - общий размер фильтра Блума по всем данным. Как правило, каждый элемент хешируется только один раз и, следовательно, устанавливается только один бит, для проверки того, был ли элемент вставлен в фильтр Блума, необходимо работать только с PE, ответственным за хэш-значение элемента. Операции одиночной вставки также могут быть выполнены эффективно, поскольку фильтр Блума только для одного PE должен быть изменен, по сравнению с репликационными фильтрами Блума, где каждый PE должен обновлять свой фильтр Блума. Распределив глобальный фильтр Блума всем PE вместо того, чтобы хранить его отдельно на каждом PE, размер фильтров может быть намного больше, что приведет к большей пропускной способности и снижению частоты ложных срабатываний.. Распределенные фильтры Блума можно использовать для улучшения алгоритмов обнаружения дубликатов, отфильтровывая наиболее «уникальные» элементы. Их можно вычислить, передать только хэши элементов, а не сами элементы, которые намного больше по объему, и удалив их из набора, уменьшив рабочую нагрузку для алгоритма обнаружения дубликатов, используемого увеличенного. Во время передачи хэшей PE ищут биты, которые более чем в одном из принимающих пакетов, так как это будет означать, что два элемента имеют одинаковый хэш и, следовательно, могут быть дубликатами. Если это происходит, сообщение, который отправили пакет с установленным битом, который может быть дубликатом. Если несколько индексов отправляются одному и тому же PE одним отправителем, может быть выгодно также кодировать индексы. Все элементы, которые не будут изменяться, должны быть изменены все элементы, для остальных элементов можно использовать алгоритм перераспределения. Сначала все элементы, которые отправляются обратно, отправляются в PE, за который их хэш. Теперь любой элемент и его дубликат гарантированно находится на одном PE. На втором этапе каждый PE использует последовательный алгоритм обнаружения дубликатов на принимающих элементах, которые составляют лишь часть количества начальных элементов. Допуская ложное срабатывание для дубликатов, объем связи можно еще больше уменьшить, поскольку PE вообще не отправляет элементы с дублированными хэшами, и вместо этого любой элемент с дублированным хешем можно просто пометить как дубликат. В такой частоте ложных срабатываний при обнаружении совпадений, как и частота ложных срабатываний используемого фильтра Блума.. Процесс фильтрации наиболее «уникальных» элементов также можно повторять несколько раз, изменяя хэш-функцию на каждом этапе фильтрации. Если используется только один шаг фильтрации, он должен архивировать небольшую частоту ложных срабатываний, однако, если фильтрация повторяется один раз, первый шаг может использовать более частоту ложных срабатываний, в то время как последний имеет более высокий уровень, но также с меньшим уровнем элементов. многие из них уже были удалены на предыдущем этапе фильтрации. Хотя использование более двух повторений может увеличить объем связи, если количество дубликатов в наборе невелико, отдача от дополнительных сложностей низка.

Репликация фильтров Блума упорядочивает свои данные с помощью хорошо известного алгоритма hypcercube для сплетен, например Сначала каждый PE вычисляет фильтр Блума по всем локальным элементам и сохранению его. Повторяя цикл, в котором на каждом шаге i PE отправляют свой локальный фильтр, который они получают по измерению, со своим локальным фильтром, можно удвоить элементы, содержащиеся в каждом фильтре Блума, на каждую итерации. После отправки и получения Блума фильтрует весь журнал $⁡ | PE | {\ displaystyle \ log | {\ text {PE}} |}$ ${\ displaystyle \ log | {\ text {PE}} |}$ измерения, каждый PE содержит глобальный фильтр Блума по всем элементам.

Репликация фильтров Блума более эффективна, когда количество запросов превышает количество элементов, проявляется в фильтре Блума, точка безубыточности по сравнению с распределенными фильтрами Блума находится примерно после $| PE | ∗ | Элементы | / log f + ⁡ | PE | {\ displaystyle | {\ text {PE}} | * | {\ text {Elements}} | / \ log _ {f ^ {\ text {+}}} | {\ text {PE}} |}$ ${\ displaystyle | {\ text {PE}} | * | {\ text {Elements}} | / \ log _ {f ^ {\ text {+}}} | {\ text {PE}} |}$ обращается с $f + {\ displaystyle f ^ {\ text {+}}}$ ${\ displaystyle f ^ {\ text {+} }}$ в качестве частоты ложных срабатываний фильтра Блума.

Синхронизация данных

Фильтры Блума могут найти для приблизительной синхронизации данных, как в Byers et al. (2004). Подсчет фильтров Блума можно использовать для приблизительного определения количества различий между двумя описаниями, и этот подход описан в Agarwal Trachtenberg (2006).

Фильтры Блумье

Chazelle et al. (2004), которое могло бы связать каждый внедренный реализованный массив . Подобно фильтрам Блума, эти структуры достигают небольших накладных расходов за счет принятия небольших вероятностей ложных срабатываний. В случае "фильтров Блумье" ложное срабатывание означает результат результата, когда ключ отсутствует на карте. Карта никогда не вернет неправильное значение для ключа, который находится на карте.

Компактные аппроксиматоры

Boldi Vigna (2005) предложили обобщение фильтров Блума на основе решетки. Компактный аппроксиматор с каждым ключом элемент решетки (стандартные фильтры, которые применяются булевой двухэлементной решетки). Вместо битового массива у них есть массив элементов решетки. При добавлении новой ассоциации между ключом и ключом решетки они вычисляют максимальное содержимое ячеек массива k, связанного с элементом решетки. При чтении значения, связанного с ключом, они вычисляют минимум значений, найденных в ячейках k, связанных с ключом. Полученное значение соответствует исходному значению сверху.

Параллельно-секционированные фильтры Блума

В этой реализации для каждой хэш-функции использовался отдельный массив. Этот метод позволяет выполнять параллельные вычисления как для вставок, так и для запросов.

Стабильные фильтры Блума

Денг и Рафией (2006) предложили стабильные фильтры Блума как вариант фильтров Блума для потоковой передачи данных. Идея заключается в том, что, поскольку нет возможности хранить всю историю потока (которая постоянно может быть бесконечной), Stable Bloom удаляет устаревшую информацию, чтобы освободить место для более новых элементов. Используется устаревшая информация удаляется, фильтр Stable Bloom вводит ложноотрицательные сообщения, которые не используются в фильтрах Bloom. Авторы показывают, что гарантируется жесткая верхняя граница частоты ложных срабатываний, и этот метод превосходит стандартные фильтры Блума с точки зрения частоты ложных срабатываний и эффективность по времени, когда предоставляется небольшое пространство и приемлемая частота ложных срабатываний.

Масштабируемые фильтры Блума

Almeida et al. (2007) может динамически адаптироваться к количеству хранимых элементов, используя при этом минимальную вероятность ложного срабатывания. Этот метод основан на последовательности стандартных стандартных фильтров. Максимальная вероятность ложного срабатывания, чтобы максимальная вероятность ложного срабатывания может быть установлена заранее, независимо от количества вставляемых элементов.

Фильтры пространственного цветения

Фильтры пространственного цветения (SBF) были предложены Palmieri, Calderoni Maio (2014) в качестве структуры данных, предназначенной для хранения местоположения информация, особенно в контексте криптографических протоколов для местоположения конфиденциальности. Однако характерной особенностью SBF является их способность хранить несколько наборов в единой структуре данных, что делает их пригодными для ряда различных сценариев приложений. Принадлежность элемента к определенному набору может быть запрошена, и вероятность ложного срабатывания зависит от: первые наборы, вводимые в фильтр во время построения, имеют более высокую вероятность набора ложных срабатываний, чем наборы, введенные в конце. Это свойство позволяет устанавливать приоритеты наборов, где могут быть сохранены наборы, содержащие более «важные» элементы.

Многослойные фильтры Блума

Многослойный фильтр Блума состоит из нескольких слоев фильтров Блума. Слоистые фильтры Bloom пропускают, сколько раз элемент был добавлен в фильтр Bloom, проверяя, сколько слоев содержит элемент. При использовании многоуровневого фильтра Блума операция проверки обычно возвращает номер самого глубокого слоя, в котором был найден элемент.

Аттенуированные фильтры Блума

Пример ослабленного фильтра Блума: поиск шаблона 11010, начиная с узла n1.

Ослабленный фильтр Блума глубины D можно рассматривать как массив D обычных фильтров Блума. В контексте обнаружения служб в сети каждый узел локально хранит обычные и ослабленные фильтры Блума. Обычный или локальный фильтр Блума указывает, какие услуги предлагает сам узел. Ослабленный фильтр уровня i указывает, какие службы могут быть найдены на узлах, удаленных на i-хоп от текущего узла. I-е создание создается путем объединения локальных фильтров Блума для узлов i-узлов, удаленных от узла.

В качестве примера возьмем небольшую сеть, показанную на графике ниже. Предположим, мы ищем службу идентификатора, который хэширует до битов 0,1 и 3 шаблон (11010). Пусть узел n1 будет отправной точкой. Сначала мы проверяем, предлагает ли услуга A пользователь n1, проверяя его локальный фильтр. Шаблоны не совпадают, мы проверяем ослабленный фильтр Блума, чтобы определить, какой узел должен быть следующим переходом. Мы видим, что n2 не предлагает услуги A, но находится на пути к узлам, которые ее предоставляют. Следовательно, мы переходим к n2 и повторяем ту же власть. Мы быстро обнаруживаем, что n3 предлагает услугу, и, следовательно, находится пункт назначения.

Используя ослабленные фильтры Блума, состоящие из нескольких уровней, можно установить услуги на расстоянии более одного перехода, избегая при этом насыщения фильтра Блума за счет ослабляющие (смещающие) биты, установленные более удаленными источниками.

Поиск химической структуры

Фильтры Блума часто используются для поиска в больших базах данных химической структуры (см. химическое сходство ). В простейшем случае элементы, добавленные к фильтру, представленные на атомном номере каждого атома, также количество и типе его связей. Этот случай слишком прост, чтобы быть полезным. Более продвинутые фильтры также кодируют количество элементов, более крупные элементы субструктуры, такие как карбокс группы, и свойства графа, такие как количество колец. В отпечатках на основе хеша-функции, используется для превращения подграфа в начальное значение PRNG, а первые выходные значения используются для установки битов в фильтре Блума.

Молекулярные отпечатки рукоположников в конце 1940-х годов как способ поиска химических структур на перфокартах. Однако только примерно в 1990 году компания Daylight Chemical Information Systems, Inc. представила метод на основе хешей для генерации битов вместо использования вычисленной таблицы. В отличие от словарного подхода, метод хеширования может назначать биты для подструктур, которые ранее не использовались. В начале 1990-х термин «отпечатокца» считался отличным от «структурных ключей», но с тех пор этот термин расширился, чтобы охватить большинство молекулярных характеристик, которые можно использовать для сравнения сходства, включая структурные ключи, разреженные отпечатки пальцев и трехмерные отпечатки пальцев.. В отличие от фильтров Блума, метод хеширования Дневной свет количеству битов, назначенных для каждой функции, функции размера функции, но в большинстве реализаций Дневной свет подобных отпечатков пальцев используется фиксированное количество битов на функцию, что делает их фильтром Блума. Исходные отпечатки пальцев Daylight можно было использовать как для сравнения, так и для проверки. Многие другие типы отпечатков пальцев, такие как популярные ECFP2, можно использовать для определения, но не для проверки, поскольку они включают в себя местные характеристики окружающей среды, которые дают ложноотрицательные результаты при использовании в качестве экрана. Это не фильтры, потому что их нельзя использовать для фильтрации.

См. Также

Портал компьютерного программирования

Примечания

Ссылки

Внешние ссылки

Викискладе есть материалы, связанные с фильтром Блума.

«Использование фильтров Блума» Подробное объяснение фильтра Блума с использованием Perl
Почему фильтры Блума работают именно так (Майкл Нильсен, 2012)
Фильтры Блума - Учебное пособие, анализ и обзор (Бластейн и Эль-Маазави, 2002) в Университете Далхаузи
Таблица количества ложных срабатываний для различных конфигураций с веб-сайта Университета Висконсина-Мэдисона
«Другие оптимальные фильтры Блума», Эли Порат (ноябрь 2007 г.) Видео Google TechTalk на YouTube