Как работают масштабируемые фильтры Блума?

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

Элементы, которые внесли свой вклад в установленные биты в первоначально созданных фильтрах, не могут быть проверены на наличие. Возможно, я не прав в моем понимании этого?

Я понимаю основные фильтры Блума. Однако я не могу обернуть голову вокруг фильтров динамического цветения.

Позвольте мне попытаться дать этому шанс, чтобы увидеть, насколько я могу убить его. :-)

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

Прежде чем мы попытаемся контролировать и оптимизировать вероятность, давайте выясним, какова вероятность для данного размера фильтра Блума.

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

Если вы увеличите количество срезов или количество битов на срез, вероятность ложных срабатываний уменьшится.

Из этого также следует, что при добавлении элементов для большего количества битов устанавливается значение 1, поэтому ложные срабатывания увеличиваются. Мы называем это «коэффициент заполнения» каждого среза.

Когда фильтр содержит большой объем данных, мы можем предположить, что вероятность ложных срабатываний для этого фильтра - это коэффициент заполнения, увеличенный до количества срезов (если бы нам нужно было фактически считать биты вместо использования отношения, это упрощается в перестановка с проблемой повторения).

Итак, как нам выяснить, как выбрать вероятность ложных срабатываний в фильтре Блума? Мы можем изменить количество срезов (что повлияет на коэффициент заполнения).

Чтобы выяснить, сколько ломтиков у нас должно быть, мы начнем с определения оптимального коэффициента заполнения для ломтика. Поскольку коэффициент заполнения определяется количеством битов в срезе, равным 1, по сравнению с количеством битов, равным 0, мы можем определить, что каждый бит останется неустановленным с вероятностью (100% - (1 / бит в срезе) ). Поскольку мы собираемся вставить несколько элементов, у нас есть еще одна перестановка с проблемой репутации, и мы расширяем вещи до ожидаемого коэффициента заполнения, который равен (100% - ((100% - (1 / бит в срезе)) ^ "элементы вставлены")). Что ж, получается, что это очень похоже на другое уравнение. В статье они связывают коэффициент заполнения с другим уравнением, поэтому оно хорошо вписывается в ряд Тейлора (1-e ^ (- n / m)). После небольшого возмущения получается, что оптимальный коэффициент заполнения всегда составляет около 50%,

Таким образом, поскольку вероятность фильтра - это коэффициент заполнения, увеличенный до количества срезов, мы можем заполнить 50% и получить P = (50%) ^ k или k = log_2 (1 / P). Затем мы можем использовать эту функцию для вычисления количества срезов, которые мы должны сгенерировать для данного фильтра в списке фильтров для масштабируемого фильтра Блума.

    def slices_count(false_positive_probability):
        return math.ceil(math.log(1 / false_positive_probability, 2))

Редактирование: После написания этого я столкнулся с упоминанием о «правиле пятидесяти процентов» при чтении динамического распределения памяти на основе системы друзей в TAoCP Vol 1, стр. 442-445, с более чистыми рассуждениями по сравнению с подгонкой кривой к (1 -e ^ (- п / м)). Кнут также ссылается на статью «Пересмотрено правило пятидесяти процентов» с небольшим фоном концепции ( pdf доступен здесь ).

Элемент находится в масштабируемом фильтре Блума, если какой-либо фильтр возвращает значение true. Следовательно, вы можете добавлять фильтры, не влияя на запросы членства для предыдущих элементов.

Чтобы гарантировать, что у вас все еще есть ложная положительная гарантия в худшем случае, добавляются новые фильтры с ошибочными положительными показателями, которые уменьшаются геометрически. Например, первый фильтр имеет ложные срабатывания p, второй rp, третьи r^2pи т.д. вероятность ложных положительный над масштабируемым цветом фильтром затем , ограниченное объединением связанным: sum_{k>=0} r^k p = p/(1-r).

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

Элементы, которые внесли свой вклад в установленные биты в первоначально созданных фильтрах, не могут быть проверены на наличие. Возможно, я не прав в моем понимании этого?

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

С точки насыщения любой новый элемент будет добавлен не в насыщенный фильтр, а в новый и более крупный подфильтр (фильтр второго уровня).

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

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