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

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

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

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

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

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

О проблеме и преимуществах хеширования см. Фильтр Блума .

Счетный фильтр Блума по сути представляет собой ту же структуру данных, что и скетчи count-min , но используются по-другому.

Возможность ложноотрицательных результатов

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

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

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

$b(l,kn,{\frac {1}{m}})={kn \choose l}({\frac {1}{m}})^{l}(1-{\frac {1}{m}})^{kn-l}$ ,

где b — биномиальное распределение. ^[2] Счетный фильтр Блума определяет, что элемент больше или равен θ , когда соответствующие счетчики k больше или равны θ. Следовательно, вероятность того, что подсчет фильтра Блума определит, что элемент больше или равен θ , равна

$p_{fp}(\theta ,k,n,m)=(1-\sum \limits _{l<\theta }b(l,kn,{\frac {1}{m}}))^{k}$ .

Это отличается от формального определения ложного срабатывания при подсчете фильтра Блума. Однако, следуя допущению в фильтре Блума, вышеуказанная вероятность определяется как ложное срабатывание фильтра Блума. Если θ =1, уравнение становится ложноположительным для фильтра Блума.

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

Для больших, но фиксированных n и m ложное срабатывание уменьшается от k =1 до точки, определенной $k_{opt}$ и увеличивается от $k_{opt}$ до положительной бесконечности. ^[3]

Ким и др. (2019) показаны численные значения $k_{opt}$ в пределах $1\leq \theta \leq 30$ . Для $\theta >30$ они предложили использовать пол или потолок ${\frac {m}{n}}(0.2037\theta +0.9176)$ .

Ссылки

^ Дик Го; Юнхао Лю; Сянъян Ли; Панлун Ян (2010). «Ложноотрицательная задача подсчета фильтра Блума» . Транзакции IEEE по знаниям и инженерии данных . 22 (5): 651–664. дои : 10.1109/TKDE.2009.209 . S2CID 3934679 .
^ Таркома, Сасу; Ротенберг, Кристиан Эстев; Лагерспец, Эмиль (2012). «Теория и практика фильтров Блума для распределенных систем». Опросы и учебные пособия IEEE по коммуникациям . 14 (1): 131–155. CiteSeerX 10.1.1.457.4228 . дои : 10.1109/surv.2011.031611.00024 . ISSN 1553-877X . S2CID 17216682 .
^ Ли, Сунгу; Ли, Ёнджу; Чон, Ёнджо; Ким, Кибеом (июль 2019 г.). «Анализ подсчетных фильтров Блума, используемых для порогового значения подсчета» . Электроника . 8 (7): 779. doi : 10.3390/electronics8070779 .

[1] Дик Го; Юнхао Лю; Сянъян Ли; Панлун Ян (2010). «Ложноотрицательная задача подсчета фильтра Блума» . Транзакции IEEE по знаниям и инженерии данных . 22 (5): 651–664. дои : 10.1109/TKDE.2009.209 . S2CID 3934679 .

[2] Таркома, Сасу; Ротенберг, Кристиан Эстев; Лагерспец, Эмиль (2012). «Теория и практика фильтров Блума для распределенных систем». Опросы и учебные пособия IEEE по коммуникациям . 14 (1): 131–155. CiteSeerX 10.1.1.457.4228 . дои : 10.1109/surv.2011.031611.00024 . ISSN 1553-877X . S2CID 17216682 .

[3] Ли, Сунгу; Ли, Ёнджу; Чон, Ёнджо; Ким, Кибеом (июль 2019 г.). «Анализ подсчетных фильтров Блума, используемых для порогового значения подсчета» . Электроника . 8 (7): 779. doi : 10.3390/electronics8070779 .

[1]

[2]

[3]