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

Вопрос:
фильтр Блума по определению имеет тенденцию к потере адекватности со временем, при увеличении фильтруемых данных.

Как это обнаруживается, как он рефрешится или убивается и строится заново?

Booben.ComВ основе Блюма одна или несколько хешфункций.
Каждая из них со временем будет давать коллизиции. Для Блюма означает ложные срабатывания.
Через какойто высокий порог, такие ложные срабатывания будут увеличиватся в геометрической прогрессии.

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

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

Да, если ФБ строится для динамического набора данных, то, естественно, его качество будет ухудшаться.
Каков критерий подмножества, на котором делать тест? Чисто эвристически брать.
Может быть накапливать статистику ложных срабатываний и затем сбрасывать фильтр в ноль и снова строить?
Я где-то читал, что при работе с дисками кэши используют что-то типа ФБ

GVF112GVFWinnipuh,

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

FYI ..

Bloom Filters by Example - http://billmill.org/bloomfilter-tutorial/
SSTable (Sorted String Table) & LSM-Tree - http://www.mezhov.com/2013/09/sstable-lsm-tree.html

С уважением,
Вадим.

Думаю, что вариант с апдейтом ФБ проходит только в частных случаях, сильно накладно, теряется эффект

skyANAWinnipuh, а смысл погружаться в Bloom Filters и LSM-trees, если последние уже развились во Fractal trees и COLA?

Может и нету, надо почитать, но в простоте тоже есть свои преимущества

skyANAWinnipuhпропущено...


Может и нету, надо почитать, но в простоте тоже есть свои преимуществаЭто какие и в простоте чего? :)

Сами ФБ в общем-то просты.

А что и где почитать про Fractal trees и COLA?
Чтобы доходчиво.

спасибо, коллеги