Фильтр Блума

Не путать с эффектом шейдера Bloom .

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

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

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

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

Пример фильтра Блума, представляющего набор { 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 независимость хэш-функций может быть ослаблена с незначительным увеличением частоты ложных срабатываний. (В частности, Dillinger & Manolios (2004b) показывают эффективность получения индексов k с использованием улучшенного двойного хеширования. и тройное хеширование — варианты двойного хеширования , которые по сути представляют собой простые генераторы случайных чисел, в которые затравлены два или три хеш-значения.)

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

заключить, что при m больших

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

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

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

вероятность того, что это 1, следовательно,

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

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

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

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

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

${\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{{kn \atop i}\right\}$

где {фигурные скобки} обозначают числа Стирлинга второго рода .

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

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

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

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

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

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

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

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

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

который можно упростить до:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

Свойства

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

Примеры

• Плодовые мухи используют модифицированную версию фильтров Блума для обнаружения новизны запахов с дополнительными функциями, включая сходство нового запаха с запахом ранее испытанных примеров, а также время, прошедшее с момента предыдущего ощущения того же запаха.
• Серверы компании Akamai Technologies , провайдера доставки контента , используют фильтры Блума, чтобы предотвратить сохранение «одноразовых чудес» в дисковых кэшах. «Чудеса одного удара» — это веб-объекты, запрошенные пользователями только один раз, и компания Akamai обнаружила, что они применяются почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса веб-объекта и кэширования этого объекта только при втором запросе предотвращает попадание чудес с одним попаданием в дисковый кэш, что значительно снижает рабочую нагрузку на диск и увеличивает частоту попаданий в дисковый кэш.
• Google Bigtable , Apache HBase , Apache Cassandra , ScyllaDB и PostgreSQL используйте фильтры Блума, чтобы сократить объем поиска на диске несуществующих строк или столбцов. Отказ от дорогостоящего поиска на диске значительно повышает производительность операции запроса к базе данных.
• Веб-браузер Google Chrome ранее использовал фильтр Блума для выявления вредоносных URL-адресов. Любой URL-адрес сначала проверялся на соответствие локальному фильтру Блума, и только если фильтр Блума возвращал положительный результат, выполнялась полная проверка URL-адреса (и пользователь предупреждался, если и это тоже давало положительный результат).
• Microsoft Bing (поисковая система) использует многоуровневые иерархические фильтры Блума для своего поискового индекса BitFunnel . Фильтры Блума обеспечивали меньшую стоимость, чем предыдущий индекс Bing, основанный на инвертированных файлах .
• Кэш Squid веб прокси - использует фильтры Блума для дайджестов кэша.
• Биткойн использовал фильтры Блума для ускорения синхронизации кошелька до тех пор, пока не были обнаружены уязвимости конфиденциальности, связанные с реализацией фильтров Блума.
• Система архивного хранения Venti использует фильтры Блума для обнаружения ранее сохраненных данных.
• Средство проверки модели SPIN использует фильтры Блума для отслеживания достижимого пространства состояний для больших проблем проверки.
• Платформа каскадной аналитики использует фильтры Блума для ускорения асимметричных соединений, когда один из объединяемых наборов данных значительно больше другого (в литературе по базам данных часто называется соединением Блума).
• Агент передачи почты Exim (MTA) использует фильтры Блума в своей функции ограничения скорости.
• Medium использует фильтры Блума, чтобы не рекомендовать статьи, которые пользователь ранее читал.
• Ethereum использует фильтры Блума для быстрого поиска журналов в блокчейне Ethereum.
• Grafana Tempo использует фильтры Блума для повышения производительности запросов за счет сохранения фильтров Блума для каждого внутреннего блока. Доступ к ним осуществляется при каждом запросе для определения блоков, содержащих данные, соответствующие заданным критериям поиска.

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

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

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

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

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

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

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

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

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

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

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

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

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

вселенной

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

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

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

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

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

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

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

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

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

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

Вариант с эффективным использованием пространства, предложенный Путце, Сандерсом и Синглером (2007), также может использоваться для реализации фильтров подсчета путем поддержки вставок и удалений.

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

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

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

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

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

Распределенный фильтр Блума Single Shot для обнаружения дубликатов с частотой ложных срабатываний: 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/|{\text{PE}}|)$ и $(p+1)*(s/|{\text{PE}}|)$, где s — общий размер фильтра Блума по всем данным. Поскольку каждый элемент хешируется только один раз и, следовательно, устанавливается только один бит, для проверки того, был ли элемент вставлен в фильтр Блума, необходимо использовать только PE, ответственный за хеш-значение элемента. Одиночные операции вставки также могут выполняться эффективно, поскольку необходимо менять фильтр Блума только одного PE, в отличие от репликации фильтров Блума, где каждый PE должен обновлять свой фильтр Блума. Распределяя глобальный фильтр Блума по всем PE вместо того, чтобы хранить его отдельно на каждом PE, размер фильтров Блума может быть намного больше, что приводит к большей емкости и снижению уровня ложных срабатываний.
Распределенные фильтры Блума можно использовать для улучшения алгоритмов обнаружения дубликатов. отфильтровывая самые «уникальные» элементы. Их можно вычислить, передав только хэши элементов, а не сами элементы, объем которых намного больше, и удалив их из набора, уменьшив рабочую нагрузку на используемый впоследствии алгоритм обнаружения дубликатов.

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

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

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

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

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

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

Блума для потоковой

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

Однако было показано что независимо от фильтра, после n вставок сумма ложных срабатываний $FP$ и ложноотрицательный $FN$ вероятности ограничены снизу

$$FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}$$

где L — количество всех возможных элементов (размер алфавита), m — объем памяти (в битах), полагая $n>m$. Этот результат показывает, что при достаточно большом L и стремлении n к бесконечности нижняя оценка сходится к $FP+FN=1$, что является характеристическим соотношением случайного фильтра. Следовательно, после достаточного количества вставок и если алфавит слишком велик для хранения в памяти (что предполагается в контексте вероятностных фильтров), фильтр не может работать лучше, чем случайный. Этот результат можно использовать, ожидая, что фильтр будет работать только со скользящим окном, а не со всем потоком. В этом случае показатель степени n в приведенной выше формуле заменяется на w , что дает формулу, которая может отклоняться от 1, если w не слишком мало.

Фильтры Bloomier

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

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

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

Фильтры Блума с параллельными разделами

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

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

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

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

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

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

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

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

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

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

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

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

Поиск

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

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

См. также

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

Ссылки

Цитируемые работы

• Агарвал, Сачин; Трахтенберг, Ари (2006). «Аппроксимация количества различий между удаленными наборами». Семинар IEEE по теории информации, 2006 г. (PDF) . Пунта-дель-Эсте, Уругвай. п. 217. CiteSeerX   10.1.1.69.1033 . дои : 10.1109/ITW.2006.1633815 . ISBN  978-1-4244-0035-5 . S2CID   2048278 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Ахмади, Махмуд; Вонг, Стефан (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.
• Болди, Паоло; Винья, Себастьяно (2005), «Изменяемые строки в Java: проектирование, реализация и облегченные алгоритмы текстового поиска» , Science of Computer Programming , 54 (1): 3–23, doi : 10.1016/j.scico.2004.05.003
• Бономи, Флавио; Митценмахер, Михаэль ; Паниграхи, Рина; Сингх, Сушил; Варгезе, Джордж (2006), «Улучшенная конструкция для подсчета фильтров Блума», Алгоритмы - ESA 2006, 14-й ежегодный европейский симпозиум (PDF) , Конспекты лекций по информатике , том. 4168, стр. 684–695, номер документа : 10.1007/11841036_61 , ISBN.  978-3-540-38875-3
• Бродер, Андрей ; Митценмахер, Майкл (2005), «Сетевые приложения фильтров Блума: обзор» (PDF) , Internet Mathematics , 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 Transactions on Information Forensics and Security , 13 (7): 1710–1721, doi : 10.1109/TIFS.2018.2799486 , hdl : 10468/5767 , ISSN   1556-6013 , S2CID   3693354
• Чанг, Фэй; Дин, Джеффри; Гемават, Санджай; Се, Уилсон; Уоллах, Дебора; Берроуз, Майк; Чандра, Тушар; Файкс, Эндрю; Грубер, Роберт (2006), «Bigtable: распределенная система хранения структурированных данных», Седьмой симпозиум по проектированию и внедрению операционных систем.
• Чарльз, Денис Ксавье; Челлапилла, Кумар (2008), «Блестящие фильтры: второй взгляд», Гальперин, Дэн; Мельхорн, Курт (ред.), Алгоритмы: ESA 2008, 16-й ежегодный европейский симпозиум, Карлсруэ, Германия, 15–17 сентября 2008 г., Труды , конспекты лекций по информатике, том. 5193, Springer, стр. 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) 10 марта 2021 г. , получено 24 октября 2019 г.
• Дэн, Фань; Рафии, Давуд (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) 2 февраля 2007 г.
• Дитцфельбингер, Мартин; Паг, Расмус (2008), «Краткие структуры данных для поиска и приблизительного членства», в Ачето, Лука; Дамгорд, Иван; Голдберг, Лесли Энн; Халлдорссон, Магнус М.; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.), Автоматы, языки и программирование: 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, Конспекты лекций по информатике 3312
• Доннет, Бенуа; Байнат, Бруно; Фридман, Тимур (2006), «Отретушированные фильтры Блума: разрешение сетевым приложениям гибко компенсировать ложные срабатывания и ложные отрицания», CoNEXT 06 - 2-я конференция по будущим сетевым технологиям , заархивировано из оригинала 17 мая 2009 г.
• Эппштейн, Дэвид ; Гудрич, Майкл Т. (2007), «Эффективная идентификация отстающих в обратных потоках данных с помощью тождеств Ньютона и обратимых фильтров Блума», Алгоритмы и структуры данных, 10-й международный семинар, WADS 2007 , Конспекты лекций по информатике, том. 4619, Springer-Verlag, стр. 637–648, arXiv : 0704.3313 , Bibcode : 2007arXiv0704.3313E
• Фан, Бин; Андерсен, Дэйв Г.; Каминский, Майкл; Митценмахер, Майкл Д. (2014), «Фильтр кукушки: практически лучше, чем Блум», Труды 10-й Международной конференции ACM по новым сетевым экспериментам и технологиям , стр. 75–88, doi : 10.1145/2674005.2674994 , ISBN  9781450332798 . Реализация с открытым исходным кодом доступна на github .
• Фан, Ли; Цао, Пей; Алмейда, Хуссара ; Бродер, Андрей (2000), «Сводный кэш: протокол совместного использования масштабируемого глобального веб-кэша» (PDF) , Транзакции IEEE/ACM в сети , 8 (3): 281–293, CiteSeerX   10.1.1.41.1487 , doi : 10.1109/90.851975 , S2CID   4779754 , заархивировано из оригинала (PDF) 22 сентября 2017 г. , получено 30 июля 2018 г. Предварительная версия появилась на SIGCOMM '98.
• Гоэль, Ашиш; Гупта, Панкадж (2010), «Запросы небольшого подмножества и фильтры Блума с использованием троичной ассоциативной памяти с приложениями» (PDF) , Обзор оценки производительности ACM SIGMETRICS , 38 : 143, CiteSeerX   10.1.1.296.6513 , doi : 10.1145/1811099.1811056
• Граф, Томас Мюллер; Лемир, Дэниел (2020), «Фильтры Xor», Журнал экспериментальной алгоритмики ACM , 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) , Конспекты лекций по информатике, том. 4168, Springer-Verlag, Конспекты лекций по информатике 4168, стр. 456–467, doi : 10.1007/11841036 , ISBN  978-3-540-38875-3 , заархивировано из оригинала (PDF) 31 января 2009 г.
• Кучерявый Ю.; Джамбене, Г.; Сталь, Д.; Барсело-Арройо, Ф.; Браун, Т.; Сирис, В. (2009), «Управление трафиком и качеством обслуживания в беспроводных мультимедийных сетях», Итоговый отчет COST 290 : 111
• Кубятович, Дж.; Биндель, Д.; Червинский, Ю.; Гилс, С.; Итон, Д.; Гуммади, Р.; Рея, С.; Уэзерспун, Х.; и др. (2000), «Oceanstore: Архитектура постоянного хранилища глобального масштаба» (PDF) , Уведомления ACM SIGPLAN : 190–201, заархивировано из оригинала (PDF) 11 марта 2012 г. , получено 1 декабря 2011 г.
• Мэггс, Брюс М .; Ситараман, Рамеш К. (июль 2015 г.), «Алгоритмические самородки в доставке контента» (PDF) , 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.
• Пальмьери, Паоло; Кальдерони, Лука; Майо, Дарио (2014), «Пространственные фильтры Блума: обеспечение конфиденциальности в приложениях, учитывающих местоположение», Proc. 10-я Международная конференция по информационной безопасности и криптологии (Inscrypt 2014) , вып. 8957, Springer-Verlag, Конспекты лекций по информатике, стр. 16–36, CiteSeerX   10.1.1.471.4759 , doi : 10.1007/978-3-319-16745-9_2 , ISBN  978-3-319-16744-2
• Порат, Эли (2009), «Оптимальная замена фильтра Блума на основе решения матриц», Фрид, Анна Э.; Морозов Андрей; Рыбальченко Андрей; Вагнер, Клаус В. (ред.), Информатика, теория и приложения: Четвертый международный симпозиум по информатике в России, CSR 2009, Новосибирск, Россия, 18–23 августа 2009 г., Труды , Конспекты лекций по информатике, том. 5675, Springer, стр. 263–273, arXiv : 0804.1845 , doi : 10.1007/978-3-642-03351-3_25 , ISBN  978-3-642-03350-6 , S2CID   3205108
• Пурнарас, Э.; Варнье, М.; Бразье, FMT (2013), «Общий и адаптивный сервис агрегации для крупномасштабных децентрализованных сетей», Моделирование сложных адаптивных систем , 1 (19): 19, doi : 10.1186/2194-3206-1-19 . Реализация прототипа доступна на github .
• Путце, Ф.; Сандерс, П .; Синглер, Дж. (2007), «Эффективные фильтры Блума для кэша, хеширования и использования пространства», Деметреску, Камил (редактор), «Экспериментальные алгоритмы», 6-й международный семинар, WEA 2007 (PDF) , конспекты лекций по информатике, том. 4525, Springer-Verlag, Конспекты лекций по информатике 4525, стр. 108–121, doi : 10.1007/978-3-540-72845-0 , ISBN  978-3-540-72844-3 , заархивировано из оригинала (PDF) 23 июня 2007 г. , получено 18 июля 2007 г.
• Роттенштрайх, Ори; Канизо, Йоси; Кесласси, Исаак (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
• Сетумадхаван, Симха; Десикан, Раджагопалан; Бургер, Дуг; Мур, Чарльз Р.; Кеклер, Стивен В. (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) 14 января 2007 г.
• Старобинский, Дэвид; Трахтенберг, Ари; Агарвал, Сачин (2003), «Эффективная синхронизация КПК» (PDF) , Транзакции IEEE на мобильных вычислениях , 2 (1): 40, CiteSeerX   10.1.1.71.7833 , doi : 10.1109/TMC.2003.1195150
• Стерн, Ульрих; Дилл, Дэвид Л. (1996), «Новая схема вероятностной проверки с эффективным использованием памяти», Труды по методам формального описания распределенных систем и протоколов связи, а также спецификация протоколов, тестирование и проверка: IFIP TC6/WG6.1 Joint International Конференция , Чепмен и Холл, Материалы конференции ИФИП, стр. 333–348, CiteSeerX   10.1.1.47.4101
• Весселс, Дуэйн (январь 2004 г.), «10.7 дайджестов кэша», Squid: The Definitive Guide (1-е изд.), O'Reilly Media, стр. 172, ИСБН  978-0-596-00162-9 , Дайджесты кэша основаны на методе, впервые опубликованном Пей Цао, под названием «Сводный кэш». Основная идея заключается в использовании фильтра Блума для представления содержимого кэша.
• Таркома, Сасу; Ротенберг, Кристиан Эстев; Лагерспец, Эмиль (2012), «Теория и практика фильтров Блума для распределенных систем», IEEE Communications Surveys & Tutorials, no. 1. (PDF) , том. 14, стр. 131–155.
• Живанг, Цен; Юнган, Сюй; Цзянь, Сан (2010), «Многослойный фильтр Блума для обнаружения повторяющихся URL-адресов», Proc. 3-я Международная конференция по передовой компьютерной теории и инженерии (ICACTE 2010) , том. 1, стр. V1–586–V1–591, doi : 10.1109/ICACTE.2010.5578947 , ISBN.  978-1-4244-6539-2 , S2CID   3108985

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

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