Как реализации фильтра Блума поддерживать в чистоте?

Question

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

Даже если у вас есть набор известного размера, в хранилище данных, использующем фильтры Блума, такие как Cassandra, меня смущает то, что данные в узле будут добавляться и удаляться, верно? Но когда вы удаляете ключ, вы не можете установить для его блоков фильтра Блума значение 0, так как это может создать ложный отрицательный результат для данных в узле, который хэширует одно или несколько таких же сегментов, что и удаленный ключ. Так что со временем фильтр как бы заполняется

Answer 1

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

Как используется в Кассандре, размер набора, охватываемого фильтром Блума, известен до создания фильтра, поэтому это не проблема.

Другой подход - Масштабируемые фильтры Блума

Answer 2

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

• Перезапись фильтра Блума
  • Вы должны сохранить старые данные
  • Вы платите цену за исполнение
• Фильтр негативного Блума
  • Гораздо дешевле, чем выше, также помогает бороться с ложными срабатываниями, если вы можете их обнаружить.
• Подсчет фильтров Блума(уменьшить счетчик)
• Buckets
  • Сохранить несколько категорированных фильтров Блума, отбрасывая категорию, когда она больше не нужна (например, «Вторник», «Среда», «Четверг», ...)
• Другие?

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