Фильтр Блума с подсчётом

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

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

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

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

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

Примечания

Литература

Fan, Li; Cao, Pei; Almeida, Jussara & Broder, Andrei (2000), Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking Т. 8 (3): 281–293, doi:10.1109/90.851975, <http://www.ece.eng.wayne.edu/~sjiang/ECE7995-07-fall/slides/summary-cache.pdf> Архивная копия от 22 сентября 2017 на Wayback Machine. A preliminary version appeared at SIGCOMM '98.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.