содержание

описывать

Фильтр Блума — это структура случайных данных с высокой эффективностью использования памяти, которая использует битовый массив для краткого представления набора и может определить, принадлежит ли элемент к этому набору. Эта эффективность фильтра Блума имеет определенную цену: при оценке того, принадлежит ли элемент определенному набору, он может ошибочно принять элементы, не принадлежащие этому набору, за принадлежащие этому набору (ложное срабатывание). Следовательно, фильтр Блума не подходит для приложений с нулевой ошибкой. В приложениях, где можно допустить низкий уровень ошибок, фильтр Блума обменивает очень мало ошибок на большую экономию места для хранения.

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

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

Фильтр Блума представляет собой битовый массив с m битами, каждый бит инициализируется 0. Определено k различных хэш-функций, каждая из которых хэширует элементы в одну из m различных позиций с равномерным случайным распределением. n — элемент, который нужно добавить в фильтр цветения. p - частота ошибок. Таким образом, соответствующими параметрами являются: m n k p (подробно позже)

Многие люди говорят, что бэкенд-инженеры — это инженеры по «добавлению, удалению, изменению и проверке», поэтому я не могу быть освобожден от обычаев. Ниже приводится объяснение с точки зрения «добавления, удаления, изменения и проверки»:

1. Процесс добавления: сначала используйте k хэш-функций, чтобы получить k битов в фильтре Блума, а затем установите для k битов значение 1.

2. Процесс запроса: то есть, чтобы определить, есть ли он в наборе, используйте k хеш-функций для его хеширования, чтобы получить k битов. Если все k битов равны 1, элемент находится в наборе; если хотя бы один из битов не равен 1, элемент отсутствует в наборе.

3. Процесс удаления: удаление элементов запрещено, потому что в этом случае соответствующие k битов будут установлены в 0, и, вероятно, будут биты, соответствующие другим элементам. Таким образом, удаление вводит ложные негативы, которые абсолютно недопустимы.

4. Процесс модификации: удаление не допускается, модификация не допускается, читатели могут принимать собственные решения.

Ложноположительный расчет скорости и доказательство

Наступает следующая кульминация, и для обратного доказательства используется математическая формула: предположим, что хеш-функция в фильтре Блума заставляет каждый элемент хэшироваться в любой из m слотов с равной вероятностью, независимо от того, в какой слот хэшируются другие элементы ( независимость). Если m - количество битов, то вероятность того, что конкретный бит не установлен в 1, когда элемент вставляется определенной хеш-функцией, составляет:

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

Теперь подсчитайте, какое значение k может минимизировать частоту ложных срабатываний для заданных m и n. Функция установки коэффициента ложных срабатываний k:

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

3 Как спроектировать фильтр Блума

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

Эта вероятность представляет собой вероятность того, что бит не будет установлен после вставки n элементов. Следовательно, чтобы поддерживать низкий уровень ошибок, использование пространства фильтра Блума должно составлять 50%.

Частота ошибок каждого параметра Bloomfilter

Суммировать

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

Справочная статья

1. Ву Ву Ву В это время почти
2. страниц. В это время Wisc. quota/~трава/бумаги…

Само введение

Личное представление: Ду Баокун, создатель федеративного обучения JD.com от 0 до 1, возглавил команду по созданию решения для федеративного обучения JD.com, реализовал сверхкрупномасштабное промышленное федеративное обучающее решение в области маркетинга электронной коммерции. , и поддерживает сверхкрупномасштабную выборку выравнивания конфиденциальности PSI. Он поддерживается многими моделями, такими как модель безопасного дерева и модель нейронной сети, и реализовал посадку в таких областях бизнеса, как рекламная сторона, создание новых точек роста бизнеса и получение значительной экономической выгоды для бизнеса.

Лично люблю изучать технологии. На основе рассмотрения полносвязного мышления и планирования технологий принятия решений существует множество областей исследований, начиная от архитектуры, данных и заканчивая алгоритмами и алгоритмическими структурами. Приветствую студентов, которым нравятся технологии, чтобы общаться со мной, по электронной почте:baokun06@163.com