Фильтр Блума с подсчётом ( англ. Counting Bloom filter ) — это обобщённая структура данных фильтра Блума , которая используется для добавления и удаления элементов в наборе данных. Как обобщённая форма фильтра Блума, ложноположительное срабатывание возможно, но ложноотрицательное — нет. Фильтр Блума с подсчётом был представлен .

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

В отличие от фильтра Блума, фильтр Блума с подсчётом представляет собой m счётчиков с несколькими битами вместо битов. Изначально, когда структура данных хранит пустое множество , все m счётчиков обнулены. Пользователь должен определить k независимых хеш-функций h ₁ , …, h _k , отображающих каждый элемент в одну из m позиций массива достаточно равномерным образом. Когда элемент добавляется или удаляется из набора данных, к элементу применяются k хеш-функций и все из k местоположений в массиве увеличиваются или уменьшаются на единицу. Операция поиска проверяет, что каждый из требуемых счётчиков не равен нулю.

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

Фильтр Блума можно рассматривать как фильтр Блума с подсчётом с размером счётчика в один бит.

Примечания

Литература

• Fan, Li; Cao, Pei; Almeida, Jussara; (2000), (PDF) , IEEE/ACM Transactions on Networking , 8 (3): 281—293, CiteSeerX , doi : от 22 сентября 2017 на Wayback Machine . A preliminary version appeared at SIGCOMM '98.