Фильтр Блума

Структура данных для приблизительного членства в наборе

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

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

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

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

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

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

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

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

Требование проектирования k различных независимых хэш-функций может быть непомерно большим для больших k . Для хорошей хэш-функции с широким выходом должно быть мало корреляций между различными битовыми полями такого хеша, если они вообще будут, поэтому этот тип хеша можно использовать для генерации нескольких «разных» хэш-функций путем нарезки его выходных данных на несколько битовых полей. В качестве альтернативы можно передать k различных начальных значений (например, 0, 1, ..., k  − 1) в хэш-функцию, которая принимает начальное значение; или добавить (или присоединить) эти значения к ключу. Для больших m и/или k независимость между хэш-функциями может быть ослаблена с незначительным увеличением частоты ложных срабатываний. ^[3] (В частности, Dillinger & Manolios (2004b) показывают эффективность вывода индексов 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] , и они будут, по-видимому, случайными, что минимизирует избыточность и максимизирует информационное содержание.

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

Вероятность ложного срабатывания p как функция количества элементов n в фильтре и размера фильтра m . Было принято оптимальное количество хэш-функций k = ( m / n ) ln 2 .

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

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

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

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

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

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

сделать вывод, что при больших m ,

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

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

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

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

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

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

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

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

Истинная вероятность ложного срабатывания, без предположения независимости, равна

${\displaystyle {\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, равна . Таким образом, вероятность того, что все k хэш-функции обнаружат свой бит, установленный в 1, равна . Кроме того, ожидаемое значение q является вероятностью того, что заданная позиция массива останется нетронутой каждой из k хэш-функций для каждого из n элементов, что равно (как указано выше) ${\displaystyle 1-q}$ ${\displaystyle (1-q)^{k}}$

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

Можно доказать, без предположения о независимости, что q очень сильно сконцентрировано вокруг своего ожидаемого значения. В частности, из неравенства Азумы–Хеффдинга они доказывают, что ^[8]

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

В связи с этим мы можем сказать, что точная вероятность ложных срабатываний составляет

${\displaystyle \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 , которое минимизирует вероятность ложного срабатывания, равно

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

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

${\displaystyle \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}}$

что можно упростить до:

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

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

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

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

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

с соответствующим числом хэш-функций k (без учета целочисленности):

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

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

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

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

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

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

Приблизительная оценка количества элементов в фильтре Блума

Число элементов в фильтре Блума можно приблизительно рассчитать по следующей формуле:

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

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

Объединение и пересечение множеств

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

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

и

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

Размер их союза можно оценить как

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

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

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

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

Характеристики

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

Примеры

• Плодовые мушки используют модифицированную версию фильтров Блума для обнаружения новых запахов с дополнительными характеристиками, включая сходство нового запаха с ранее испытанными образцами, а также время, прошедшее с момента предыдущего опыта восприятия того же запаха. ^[12]
• Серверы Akamai Technologies , поставщика услуг доставки контента , используют фильтры Блума для предотвращения сохранения «одноразовых чудес» в кэшах дисков. Одноразовые чудеса — это веб-объекты, запрошенные пользователями всего один раз, что, как обнаружила компания Akamai, относится почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса на веб-объект и кэширования этого объекта только при втором запросе предотвращает попадание одноразовых чудес в кэш диска, значительно снижая нагрузку на диск и увеличивая частоту попаданий в кэш диска. ^[13]
• Google Bigtable , Apache HBase , Apache Cassandra , ScyllaDB и PostgreSQL ^[14] используют фильтры Блума для сокращения дисковых поисков для несуществующих строк или столбцов. Избежание дорогостоящих дисковых поисков значительно увеличивает производительность операции запроса базы данных. ^[15]
• Веб-браузер Google Chrome ранее использовал фильтр Bloom для определения вредоносных URL-адресов. Любой URL-адрес сначала проверялся с помощью локального фильтра Bloom, и только если фильтр Bloom возвращал положительный результат, выполнялась полная проверка URL-адреса (и пользователь предупреждался, если и это возвращало положительный результат). ^{[16] [17]}
• Microsoft Bing (поисковая система) использует многоуровневые иерархические фильтры Блума для своего поискового индекса BitFunnel . Фильтры Блума обеспечивали более низкую стоимость, чем предыдущий индекс Bing, который был основан на инвертированных файлах . ^[18]
• Кэш -сервер Squid Web Proxy использует фильтры Блума для дайджестов кэша. ^[19]
• Биткоин использовал фильтры Блума для ускорения синхронизации кошелька, пока не были обнаружены уязвимости конфиденциальности при внедрении фильтров Блума. ^[20]
• Архивная система хранения Venti использует фильтры Блума для обнаружения ранее сохраненных данных. ^[21]
• Средство проверки модели SPIN использует фильтры Блума для отслеживания достижимого пространства состояний для больших задач проверки. ^[22]
• Структура каскадной аналитики использует фильтры Блума для ускорения асимметричных соединений, где один из объединенных наборов данных значительно больше другого (в литературе по базам данных это часто называется соединением Блума). ^[23]
• Агент электронной почты Exim (MTA) использует фильтры Блума в своей функции ограничения скорости. ^{[ необходима ссылка ]}
• Medium использует фильтры Блума, чтобы не рекомендовать статьи, которые пользователь уже читал. ^{[24] [ источник, созданный пользователем? ]}
• Ethereum использует фильтры Блума для быстрого поиска журналов в блокчейне Ethereum.
• Grafana Tempo использует фильтры Блума для улучшения производительности запросов, сохраняя фильтры Блума для каждого внутреннего блока. Они доступны для каждого запроса, чтобы определить блоки, содержащие данные, которые соответствуют заданным критериям поиска ^[25]

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

Классические фильтры Блума используют биты пространства на вставленный ключ, где — частота ложных срабатываний фильтра Блума. Однако пространство, которое строго необходимо для любой структуры данных, играющей ту же роль, что и фильтр Блума, — только на ключ. ^[26] Следовательно, фильтры Блума используют на 44% больше пространства, чем эквивалентная оптимальная структура данных. ${\displaystyle 1.44\log _{2}(1/\varepsilon )}$ ${\displaystyle \varepsilon }$ ${\displaystyle \log _{2}(1/\varepsilon )}$

Паг и др. предлагают структуру данных, которая использует биты, поддерживая при этом постоянные амортизированные операции с ожидаемым временем. ^[27] Их структура данных в основном теоретическая, но она тесно связана с широко используемым фильтром факторизации , который может быть параметризован для использования битов пространства для произвольного параметра , поддерживая при этом операции с временем. ^[28] Преимущества фильтра факторизации по сравнению с фильтром Блума включают в себя локальность ссылок и способность поддерживать удаления. ${\textstyle (1+o(1))n\log _{2}(1/\epsilon )+O(n)}$ ${\displaystyle (1+\delta )n\log \epsilon ^{-1}+3n}$ ${\displaystyle \delta >0}$ ${\displaystyle O(\delta ^{-2})}$

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

Многие альтернативы фильтрам Блума, включая фильтры коэффициентов и фильтры кукушки , основаны на идее хеширования ключей для случайных -битных отпечатков пальцев и последующего сохранения этих отпечатков пальцев в компактной хеш-таблице. Эта техника, впервые представленная Картером и др. в 1978 году, ^[26] основана на том факте, что компактные хеш-таблицы могут быть реализованы для использования примерно на бит меньше пространства, чем их некомпактные аналоги. Используя краткие хеш-таблицы, использование пространства может быть сокращено до бит ^[30] , при этом поддерживая операции с постоянным временем в широком диапазоне режимов параметров. ${\displaystyle (\log n+\log \epsilon ^{-1})}$ ${\displaystyle n\log n}$ ${\displaystyle n\log _{2}(e/\epsilon )+o(n)}$

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

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

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

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

Существует более 60 вариантов фильтров Блума, множество обзоров в этой области и продолжающееся бурление приложений (см., например, Luo и др. ^[31] ). Некоторые из вариантов достаточно сильно отличаются от первоначального предложения, чтобы быть нарушениями или ответвлениями исходной структуры данных и ее философии. ^[31] Обработка, которая объединяет фильтры Блума с другими работами по случайным проекциям , сжатому зондированию и локально-чувствительному хешированию, еще предстоит сделать (хотя см. Dasgupta и др ^{. [32]} для одной попытки, вдохновленной нейронаукой).

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

Использование фильтра Блума для предотвращения сохранения одноразовых чудес в веб-кэше снизило скорость записи на диск почти наполовину, уменьшив нагрузку на диски и потенциально увеличив производительность дисков. ^[13]

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

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

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

В качестве альтернативы, начальный фильтр Блума может быть построен стандартным способом, а затем, с конечным и легко перечислимым доменом, все ложные срабатывания могут быть исчерпывающе найдены, а затем второй фильтр Блума построен из этого списка; ложные срабатывания во втором фильтре аналогичным образом обрабатываются путем построения третьего и т. д. Поскольку вселенная конечна, а набор ложных срабатываний строго сокращается с каждым шагом, эта процедура приводит к конечному каскаду фильтров Блума, которые (в этом замкнутом конечном домене) будут производить только истинно положительные и истинно отрицательные результаты. Чтобы проверить членство в каскаде фильтров, запрашивается начальный фильтр, и, если результат положительный, затем обращается ко второму фильтру и т. д. Эта конструкция используется в CRLite , предлагаемом механизме распределения статуса отзыва сертификатов для Web PKI, а прозрачность сертификатов используется для закрытия набора существующих сертификатов. ^[34]

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

Фильтры подсчета предоставляют способ реализовать операцию удаления в фильтре Блума без повторного создания фильтра заново. В фильтре подсчета позиции массива (корзины) расширяются от однобитовых до многобитовых счетчиков. Фактически, обычные фильтры Блума можно рассматривать как фильтры подсчета с размером корзины в один бит. Фильтры подсчета были введены Фаном и др. (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 до определенной точки и увеличивается от до положительной бесконечности, и находится в зависимости от порогового значения подсчета. ^[35] ${\displaystyle k_{opt}}$ ${\displaystyle k_{opt}}$ ${\displaystyle k_{opt}}$

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

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

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

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

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

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

Во время передачи хэшей PE ищут биты, которые установлены более чем в одном из принимающих пакетов, так как это означало бы, что два элемента имели одинаковый хэш и, следовательно, могли быть дубликатами. Если это происходит, сообщение, содержащее индекс бита, который также является хешем элемента, который может быть дубликатом, отправляется PE, отправившим пакет с установленным битом. Если несколько индексов отправляются одному и тому же PE одним отправителем, может быть выгодно также кодировать индексы. Все элементы, которым не был отправлен их хэш, теперь гарантированно не являются дубликатами и не будут оцениваться далее, для оставшихся элементов может использоваться алгоритм перераспределения ^[39] . Сначала все элементы, которым было отправлено их хэш-значение, отправляются PE, за который отвечает их хэш. Теперь любой элемент и его дубликат гарантированно находятся на одном PE. На втором этапе каждый PE использует последовательный алгоритм для обнаружения дубликатов на принимающих элементах, которые составляют лишь часть от количества исходных элементов. Допуская частоту ложных срабатываний для дубликатов, можно еще больше сократить объем коммуникации, поскольку PE вообще не нужно отправлять элементы с дублированными хэшами, а вместо этого любой элемент с дублированным хешем можно просто пометить как дубликат. В результате частота ложных срабатываний для обнаружения дубликатов такая же, как частота ложных срабатываний используемого фильтра Блума.

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

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

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

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

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

Фильтры Блума для потоковых данных

Фильтры Блума можно адаптировать к контексту потоковых данных. Например, Дэн и Рафии (2006) предложили фильтры Стабильного Блума, которые состоят из подсчитывающего фильтра Блума, где вставка нового элемента устанавливает связанные счетчики в значение c , а затем только фиксированное количество счетчиков s уменьшается на 1, поэтому память в основном содержит информацию о последних элементах (интуитивно можно предположить, что время жизни элемента внутри SBF из N счетчиков составляет около ). Другое решение — фильтр Старения Блума, который состоит из двух фильтров Блума, каждый из которых занимает половину общей доступной памяти: когда один фильтр заполнен, второй фильтр стирается, и новые элементы затем добавляются к этому новому пустому фильтру. ^[41] ${\displaystyle c{\tfrac {s}{N}}}$

Однако было показано ^[42] , что независимо от фильтра, после n вставок сумма ложноположительных и ложноотрицательных вероятностей ограничена снизу величиной , где L — количество всех возможных элементов (размер алфавита), m — размер памяти (в битах), предполагая . Этот результат показывает, что при достаточно большом L и стремлении n к бесконечности нижняя граница сходится к , что является характерным отношением случайного фильтра. Следовательно, после достаточного количества вставок и если алфавит слишком велик для хранения в памяти (что предполагается в контексте вероятностных фильтров), фильтр не может работать лучше случайности. Этот результат можно использовать, ожидая, что фильтр будет работать только со скользящим окном, а не со всем потоком. В этом случае показатель степени n в приведенной выше формуле заменяется на w , что дает формулу, которая может отклоняться от 1, если w не слишком мало. ${\displaystyle FP}$ ${\displaystyle FN}$ $${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$$ ${\displaystyle n>m}$ ${\displaystyle FP+FN=1}$

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

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

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

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

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

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

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

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

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

Пространственные фильтры Блума (SBF) были первоначально предложены Пальмиери, Кальдерони и Майо (2014) как структура данных, предназначенная для хранения информации о местоположении , особенно в контексте криптографических протоколов для обеспечения конфиденциальности местоположения . Однако основной характеристикой SBF является их способность хранить несколько наборов в одной структуре данных, что делает их пригодными для ряда различных сценариев применения. ^[44] Членство элемента в определенном наборе может быть запрошено, а вероятность ложного срабатывания зависит от набора: первые наборы, которые будут введены в фильтр во время построения, имеют более высокие вероятности ложного срабатывания, чем наборы, введенные в конце. ^[45] Это свойство позволяет приоритезировать наборы, где наборы, содержащие более «важные» элементы, могут быть сохранены.

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

• Скетч Count–min  – Вероятностная структура данных в информатике
• Хеширование признаков  – векторизация признаков с использованием хеш-функции
• MinHash  — техника интеллектуального анализа данных
• Фильтр коэффициентов
• Пропустить список  – Вероятностная структура данных
• Фильтры Блума в биоинформатике
• Фильтр «Кукушка»  – Структура данных для приблизительного членства в наборе

Ссылки

Цитаты

1. Блум (1970).
2. Бономи и др. (2006).
3. Диллинджер и Манолиос (2004a); Кирш и Митценмахер (2006).
4. Митценмахер и Упфаль (2005).
5. Блюстейн и Эль-Маазави (2002), стр. 21–22.
6. Гопинатан, Киран; Сергей, Илья (2020-07-21). «Сертификация определенности и неопределенности в приблизительных структурах запросов на членство». Computer Aided Verification . Lecture Notes in Computer Science. Vol. 12225. Springer, Cham. pp. 279–303. doi :10.1007/978-3-030-53291-8_16. ISBN 978-3-030-53290-1. ЧМЦ  7363400 .
7. Митценмахер и Упфал (2005), стр. 109–111, 308.
8. Митценмахер и Упфал (2005), стр. 308.
9. Старобински, Трахтенберг и Агарвал (2003)
10. Гоэль и Гупта (2010)
11. Swamidass, S. Joshua; Baldi, Pierre (2007). «Математическая коррекция мер сходства отпечатков пальцев для улучшения химического поиска». Journal of Chemical Information and Modeling . 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  . 
13. Мэггс и Ситараман (2015).
14. "Bloom index contrib module". Postgresql.org. 2016-04-01. Архивировано из оригинала 2018-09-09 . Получено 2016-06-18 .
15. Чанг и др. (2006); Apache Software Foundation (2012).
16. Якунин, Алекс (2010-03-25). "Блог Алекса Якунина: Хорошее приложение фильтра Блума". Blog.alexyakunin.com. Архивировано из оригинала 2010-10-27 . Получено 2014-05-31 .
17. "Проблема 10896048: Переход безопасного просмотра с фильтра Блума на набор префиксов. - Обзор кода". Chromiumcodereview.appspot.com . Получено 2014-07-03 .
18. Гудвин, Боб; Хопкрофт, Майкл; Луу, Дэн; Клеммер, Алекс; Курмей, Михаэла; Элникети, Самех; Юйсян, Хэ (2017). «BitFunnel: Пересмотр сигнатур для поиска» (PDF) . Труды 40-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска . стр. 605–614. doi : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8. S2CID  20123252.
19. Весселс (2004).
20. "Фильтр Блума | Глоссарий River". River Financial . Получено 14.11.2020 .
21. "Plan 9 /sys/man/8/venti". Plan9.bell-labs.com. Архивировано из оригинала 2014-08-28 . Получено 2014-05-31 .
22. «Спин — Формальная проверка».
23. Маллин (1990).
24. "Что такое фильтры Блума?". Medium. 2015-07-15 . Получено 2015-11-01 .
25. "Grafana Tempo Documentation - Caching". Grafana . Получено 2022-11-16 .
26. Картер, Ларри; Флойд, Роберт; Гилл, Джон; Марковски, Джордж; Вегман, Марк (1978). «Точные и приближенные тестеры членства». Труды десятого ежегодного симпозиума ACM по теории вычислений — STOC '78 . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 59–65. doi :10.1145/800133.804332. S2CID  6465743.
27. Паг, Паг и Рао (2005).
28. Бендер, Майкл А.; Фарах-Колтон, Мартин; Джонсон, Роб; Кранер, Рассел; Кушмаул, Брэдли К.; Медьедович, Джейла; Монтес, Пабло; Шетти, Прадип; Спиллейн, Ричард П.; Задок, Эрез (июль 2012 г.). «Не бейте». Труды VLDB Endowment . 5 (11): 1627–1637. doi :10.14778/2350229.2350275. ISSN  2150-8097. S2CID  47180056.
29. Even, Tomer; Even, Guy; Morrison, Adam (март 2022 г.). «Префиксный фильтр». Труды VLDB Endowment . 15 (7): 1311–1323. doi :10.14778/3523210.3523211. ISSN  2150-8097.
30. Бендер, Майкл А.; Фарах-Колтон, Мартин; Кусзмаул, Джон; Кусзмаул, Уильям; Лю, Минмоу (09.06.2022). «Об оптимальном соотношении времени и пространства для хэш-таблиц». Труды 54-го ежегодного симпозиума ACM SIGACT по теории вычислений . Нью-Йорк, США: ACM. С. 1284–1297. arXiv : 2111.00602 . doi : 10.1145/3519935.3519969. hdl : 1721.1/146419 . ISBN 9781450392648. S2CID  240354692.
31. Luo, Lailong; Guo, Deke; Ma, Richard TB; Rottenstreich, Ori; Luo, Xueshan (13 апреля 2018 г.). «Оптимизация фильтра Блума: проблемы, решения и сравнения». arXiv : 1804.04777 [cs.DS].
32. Дасгупта, Санджой; Шихан, Тимоти К.; Стивенс, Чарльз Ф.; Навлакхае, Сакет (2018). «Нейронная структура данных для обнаружения новизны». Труды Национальной академии наук . 115 (51): 13093–13098. Bibcode : 2018PNAS..11513093D. doi : 10.1073/pnas.1814448115 . PMC 6304992. PMID  30509984 . 
33. Поцелуй, СЗ; Хоссу, Э.; Таполькай, Дж.; Роньяи, Л.; Роттенштрайх, О. (2018). «Фильтр Блума с ложноположительной свободной зоной» (PDF) . IEEE Труды INFOCOM . Проверено 4 декабря 2018 г.
34. Лариш, Джеймс; Чоффнес, Дэвид; Левин, Дэйв; Мэггс, Брюс М.; Мислов, Алан; Уилсон, Кристо (2017). «CRLite: масштабируемая система для передачи всех отзыва TLS всем браузерам». Симпозиум IEEE по безопасности и конфиденциальности (SP) 2017 г. стр. 539–556. doi : 10.1109/sp.2017.17 . ISBN 978-1-5090-5533-3. S2CID  3926509.
35. Ким, Кибеом; Чон, Ёнджо; Ли, Ёнджо; Ли, Сунгу (2019-07-11). «Анализ подсчета фильтров Блума, используемых для порогового значения подсчета». Электроника . 8 (7): 779. doi : 10.3390/electronics8070779 . ISSN  2079-9292.
36. Пурнарас, Варнье и Бразье (2013).
37. Сандерс, Питер; Шлаг, Себастьян; Мюллер, Инго (2013). «Эффективные алгоритмы коммуникации для фундаментальных проблем больших данных». Международная конференция IEEE по большим данным 2013 г. С. 15–23. doi :10.1109/BigData.2013.6691549. ISBN 978-1-4799-1293-3. S2CID  15968541.
38. Шлаг, Себастьян (2013). «Распределенное удаление дубликатов». Технологический институт Карлсруэ .
39. Шатдал, Амбудж; Джеффри Ф. Нотон (1994). «Обработка агрегатов в параллельных системах баз данных». Университет Висконсин-Мэдисон, кафедра компьютерных наук : 8.
40. В. Кумар; А. Грама; А. Гупта; Г. Карипис (1994). Введение в параллельные вычисления. Проектирование и анализ алгоритмов . Benjamin/Cummings.
41. Юн, МёнКён (2010). «Фильтр старения Блума с двумя активными буферами для динамических наборов». Труды IEEE по знаниям и инжинирингу данных . 22 (1): 134–138. doi :10.1109/TKDE.2009.136. S2CID  15922054.
42. Жеро-Стюарт, Реми; Ломбард-Плате, Мариус; Наккаш, Дэвид (2020). «Приближение к оптимальному обнаружению дубликатов в скользящем окне». Вычисления и комбинаторика . Конспект лекций по информатике. Том 12273. С. 64–84. arXiv : 2005.04740 . doi :10.1007/978-3-030-58150-3_6. ISBN 978-3-030-58149-7. S2CID  218581915.
43. Кирш, Адам; Митценмахер†, Майкл. «Меньше хеширования, та же производительность: создание лучшего фильтра Блума» (PDF) . Гарвардская школа инженерии и прикладных наук . Wiley InterScience.
44. Кальдерони, Палмьери и Майо (2015).
45. Кальдерони, Палмьери и Майо (2018).
46. Чживанг, Юнган и Цзянь (2010).
47. Кучеряви и др. (2009).
48. Кубятович и др. (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: location missing publisher (link)
• Ахмади, Махмуд; Вонг, Стефан (2007), «Архитектура кэша для подсчета фильтров Блума», 15-я международная конференция по сетям (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) , Information Processing Letters , 101 (6): 255–261, doi : 10.1016/j.ipl.2006.10.007, hdl : 1822/6627
• Apache Software Foundation (2012), «11.6. Проектирование схемы», Справочное руководство Apache HBase, редакция 0.94.27
• Блум, Бертон Х. (1970), «Компромиссы пространства/времени в хэш-кодировании с допустимыми ошибками», Communications of the ACM , 13 (7): 422–426, CiteSeerX  10.1.1.641.9096 , doi :10.1145/362686.362692, S2CID  7931252
• Блюстейн, Джеймс; Эль-Маазави, Амаль (2002), «Оптимальный случай для общих фильтров Блума», Фильтры Блума — Учебное пособие, Анализ и Обзор, Факультет компьютерных наук Университета Далхаузи, стр. 1–31
• Boldi, Paolo; Vigna, Sebastiano (2005), «Изменяемые строки в Java: проектирование, реализация и легкие алгоритмы текстового поиска», Science of Computer Programming , 54 (1): 3–23, doi :10.1016/j.scico.2004.05.003
• Бономи, Флавио; Митценмахер, Майкл ; Паниграхи, Рина; Сингх, Сушил; Варгезе, Джордж (2006), «Улучшенная конструкция для подсчета фильтров Блума», Алгоритмы – ESA 2006, 14-й ежегодный европейский симпозиум (PDF) , Lecture Notes in Computer Science , т. 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 Transactions on Networking , 12 (5): 767, CiteSeerX  10.1.1.207.1563 , doi :10.1109/TNET.2004.836103, S2CID  47088273
• Кальдерони, Лука; Пальмиери, Паоло; Майо, Дарио (2015), «Конфиденциальность местоположения без взаимного доверия: пространственный фильтр Блума» (PDF) , Computer Communications , 68 : 4–16, doi : 10.1016/j.comcom.2015.06.011, hdl : 10468/4762, ISSN  0140-3664
• Кальдерони, Лука; Пальмиери, Паоло; Майо, Дарио (2018), «Вероятностные свойства пространственных фильтров Блума и их значимость для криптографических протоколов», Труды IEEE по информационной криминалистике и безопасности , 13 (7): 1710–1721, doi : 10.1109/TIFS.2018.2799486, hdl : 10468/5767 , ISSN  1556-6013, S2CID  3693354
• Чанг, Фэй; Дин, Джеффри; Гемават, Санджай; Хси, Уилсон; Уоллах, Дебора; Берроуз, Майк; Чандра, Тушар; Файкс, Эндрю; Грубер, Роберт (2006), «Bigtable: распределенная система хранения структурированных данных», Седьмой симпозиум по проектированию и внедрению операционных систем
• Charles, Denis Xavier; Chellapilla, Kumar (2008), "Фильтры Блумьера: второй взгляд", в Halperin, Dan; Mehlhorn, Kurt (ред.), Algorithms: ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008, Proceedings , Lecture Notes in Computer Science, vol. 5193, Springer, pp. 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) 2021-03-10 , извлечено 2019-10-24
• Дэн, Фань; Рафии, Давуд (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
• Dietzfelbinger, Martin; Pagh, Rasmus (2008), «Краткие структуры данных для поиска и приблизительного членства», в Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (ред.), Автоматы, языки и программирование: 35-й международный коллоквиум, ICALP 2008, Рейкьявик, Исландия, 7–11 июля 2008 г., Труды, часть I, трек A: Алгоритмы, автоматы, сложность и игры , заметки лекций по информатике, т. 5125, Springer, стр. 385–396, arXiv : 0803.3693 , doi :10.1007/978-3-540-70575-8_32, ISBN 978-3-540-70574-1, S2CID  1699996
• Диллинджер, Питер К.; Манолиос, Панайотис (2004a), «Быстрая и точная проверка битового состояния для SPIN», Труды 11-го Международного семинара Spin по программному обеспечению для проверки моделей, Springer-Verlag, Конспект лекций по информатике 2989
• Диллинджер, Питер К.; Манолиос, Панайотис (2004b), «Фильтры Блума в вероятностной верификации», Труды 5-й Международной конференции по формальным методам в автоматизированном проектировании, Springer-Verlag, Lecture Notes in Computer Science 3312
• Доннет, Бенуа; Байнат, Бруно; Фридман, Тимур (2006), «Ретушированные фильтры Блума: как сетевые приложения могут гибко компенсировать ложные положительные и ложные отрицательные результаты», CoNEXT 06 – 2-я конференция по будущим сетевым технологиям, архивировано с оригинала 17.05.2009
• Эппштейн, Дэвид ; Гудрич, Майкл Т. (2007), «Эффективная по пространству идентификация отставших в потоках данных с круговым движением с помощью тождеств Ньютона и обратимых фильтров Блума», Алгоритмы и структуры данных, 10-й международный семинар, WADS 2007 , Lecture Notes in Computer Science, т. 4619, Springer-Verlag, стр. 637–648, arXiv : 0704.3313 , Bibcode : 2007arXiv0704.3313E
• Фэн, Бин; Андерсен, Дэйв Г.; Камински, Майкл; Митценмахер, Майкл Д. (2014), «Фильтр кукушки: практически лучше, чем Блум», Труды 10-й Международной конференции ACM по новым сетевым экспериментам и технологиям , стр. 75–88, doi : 10.1145/2674005.2674994 , ISBN 9781450332798. Реализация с открытым исходным кодом доступна на github.
• Fan, Li; Cao, Pei; Almeida, Jussara ; Broder, Andrei (2000), «Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol» (PDF) , IEEE/ACM Transactions on Networking , 8 (3): 281–293, 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 Performance Evaluation Review , 38 : 143, CiteSeerX  10.1.1.296.6513 , doi : 10.1145/1811099.1811056
• Граф, Томас Мюллер; Лемир, Дэниел (2020), «Фильтры Xor», ACM Journal of Experimental Algorithmics , 25 : 1–16, arXiv : 1912.08258 , Bibcode : 2019arXiv191208258M, doi : 10.1145/3376122, S2CID  209405019
• Гранди, Фабио (2018), «Об анализе фильтров Блума» (PDF) , Information Processing Letters , 129 : 35–39, doi :10.1016/j.ipl.2017.09.004
• Кирш, Адам; Митценмахер, Майкл (2006), «Меньше хеширования, та же производительность: создание лучшего фильтра Блума», в Азар, Йосси; Эрлебах, Томас (ред.), Алгоритмы – ESA 2006, 14-й ежегодный европейский симпозиум (PDF) , Lecture Notes in Computer Science, т. 4168, Springer-Verlag, Lecture Notes in Computer Science 4168, стр. 456–467, doi :10.1007/11841036, ISBN 978-3-540-38875-3, заархивировано из оригинала (PDF) 2009-01-31
• Кучерявый Ю.; Джамбене, Г.; Сталь, Д.; Барсело-Арройо, Ф.; Браун, Т.; Сирис, В. (2009 г.), «Управление трафиком и качеством обслуживания в беспроводных мультимедийных сетях», Итоговый отчет COST 290 : 111
• Кубятович, Дж.; Биндель, Д.; Червински, Й.; Гилс, С.; Итон, Д.; Гуммади, Р.; Риа, С.; Уэзерспун, Х.; и др. (2000), «Oceanstore: архитектура для глобального постоянного хранилища» (PDF) , уведомления ACM SIGPLAN : 190–201, архивировано из оригинала (PDF) 2012-03-11 , извлечено 2011-12-01
• Maggs, Bruce M .; Sitaraman, Ramesh K. (июль 2015 г.), «Алгоритмические крупицы в доставке контента» (PDF) , ACM SIGCOMM Computer Communication Review , 45 (3): 52–66, CiteSeerX  10.1.1.696.9236 , doi : 10.1145/2805789.2805800, S2CID  65760, архивировано из оригинала (PDF) 14 августа 2021 г.
• Митценмахер, Майкл ; Упфал, Эли (2005), Вероятность и вычисления: Рандомизированные алгоритмы и вероятностный анализ, Cambridge University Press, стр. 107–112, ISBN 9780521835404
• Мортенсен, Кристиан Ворм; Паг, Расмус ; Патраску, Михай (2005), «О динамическом диапазоне отчетов в одном измерении», Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений , стр. 104–111, arXiv : cs/0502032 , doi :10.1145/1060590.1060606, ISBN 978-1581139600, S2CID  56473
• Маллин, Джеймс К. (1990), «Оптимальные полусоединения для распределенных систем баз данных», IEEE Transactions on Software Engineering , 16 (5): 558–560, doi :10.1109/32.52778
• Паг, Анна; Паг, Расмус ; Рао, С. Шриниваса (2005), «Оптимальная замена фильтра Блума», Труды шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (PDF) , стр. 823–829
• Palmieri, Paolo; Calderoni, Luca; Maio, Dario (2014), «Пространственные фильтры Блума: обеспечение конфиденциальности в приложениях с учетом местоположения», Proc. 10th International Conference on Information Security and Cryptology (Inscrypt 2014) , т. 8957, Springer-Verlag, Lecture Notes in Computer Science, стр. 16–36, CiteSeerX  10.1.1.471.4759 , doi : 10.1007/978-3-319-16745-9_2, ISBN 978-3-319-16744-2
• Porat, Ely (2009), "Оптимальная замена фильтра Блума на основе решения матриц", в Frid, Anna E.; Morozov, Андрей; Rybalchenko, Андрей; Wagner, Klaus W. (ред.), Computer Science, Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Новосибирск, Россия, 18–23 августа 2009 г., Proceedings , Lecture Notes in Computer Science, т. 5675, Springer, стр. 263–273, arXiv : 0804.1845 , doi :10.1007/978-3-642-03351-3_25, ISBN 978-3-642-03350-6, S2CID  3205108
• Pournaras, E.; Warnier, M.; Brazier, FMT (2013), "Универсальная и адаптивная служба агрегации для крупномасштабных децентрализованных сетей", Complex Adaptive Systems Modeling , 1 (19): 19, doi : 10.1186/2194-3206-1-19. Реализация прототипа доступна на github.
• Putze, F.; Sanders, P .; Singler, J. (2007), «Кэш-, хэш- и пространственно-эффективные фильтры Блума», в Demetrescu, Camil (ред.), Experimental Algorithms, 6th International Workshop, WEA 2007 (PDF) , Lecture Notes in Computer Science, т. 4525, Springer-Verlag, Lecture Notes in Computer Science 4525, стр. 108–121, doi :10.1007/978-3-540-72845-0, ISBN 978-3-540-72844-3, заархивировано из оригинала (PDF) 2007-06-23 , извлечено 2007-07-18
• Роттенстрейх, Ори; Канизо, Йосси; Кесласси, Айзек (2012), «Фильтр Блума с переменным приращением», 31-я ежегодная международная конференция IEEE по компьютерным коммуникациям, 2012, Infocom 2012 (PDF) , стр. 1880–1888, CiteSeerX  10.1.1.174.7165 , doi :10.1109/INFCOM.2012.6195563, ISBN 978-1-4673-0773-4
• Sethumadhavan, Simha; Desikan, Rajagopalan; Burger, Doug; Moore, Charles R.; Keckler, Stephen W. (2003), «Масштабируемое аппаратное устранение неоднозначности памяти для процессоров с высоким ILP», 36-й ежегодный международный симпозиум 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) 2007-01-14
• Старобински, Дэвид; Трахтенберг, Ари; Агарвал, Сачин (2003), «Эффективная синхронизация КПК» (PDF) , IEEE Transactions on Mobile Computing , 2 (1): 40, 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 Кэш-дайджесты», Squid: The Definitive Guide (1-е изд.), O'Reilly Media, стр. 172, ISBN 978-0-596-00162-9, Cache Digests основаны на технике, впервые опубликованной Пэй Цао, которая называется Summary Cache. Основная идея заключается в использовании фильтра Блума для представления содержимого кэша.
• Таркома, Сасу; Ротенберг, Кристиан Эстеве; Лагершпец, Эмиль (2012), «Теория и практика фильтров Блума для распределенных систем», IEEE Communications Surveys & Tutorials, № 1. (PDF) , том 14, стр. 131–155
• Zhiwang, Cen; Jungang, Xu; Jian, Sun (2010), «Многослойный фильтр Блума для обнаружения дублированных URL», Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010) , т. 1, стр. V1–586–V1–591, doi :10.1109/ICACTE.2010.5578947, ISBN 978-1-4244-6539-2, S2CID  3108985

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

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