Русская Википедия:Кукушкин фильтр
Кукушкин фильтр (Шаблон:Lang-en) — это эффективная по памяти вероятностная структура данных, которая используется для проверки, принадлежит ли элемент множеству, подобно фильтру Блума. Возможны ложноположительные результаты, но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума[1].
Кукушкин фильтр впервые был описан в 2014 году[2].
Алгоритм
Кукушкин фильтр использует <math>n</math>-канальную множественно-ассоциативную хеш-таблицу, основанную на кукушкином хешировании, для хранения цифровых отпечатков всех элементов (в каждой корзине хеш-таблицы может храниться до <math>n</math> записей). В частности, два индекса потенциальных корзин <math>i</math> и <math>j</math> в таблице для данного элемента <math>x</math> вычисляются с помощью следующих двух хеш-функций (называется кукушкино хеширование с частичным ключом, Шаблон:Lang-en)[2]):
- <math>i = h_1(x)=\text{hash}(x)</math>
- <math>j = h_2(x)=h_1(x)\oplus\text{hash}(\text{fingerprint}(x))</math>
Применение двух вышеуказанных хеш-функций для построения кукушкиных хеш-таблиц позволяет перемещать элементы только на основе цифрового отпечатка, когда узнать исходный элемент <math>x</math> невозможно. В результате при вставке нового элемента, который требует перемещения существующего элемента <math>y</math>, другое возможное местоположение <math>j</math> в таблице для элемента <math>y</math>, вытесненного из корзины <math>i,</math> вычисляется по формуле
- <math>j = i\oplus\text{hash}(\text{fingerprint}(y))</math>
Основанная на кукушкином хешировании с частичным ключом хеш-таблица может обеспечить как высокую степень использования (благодаря кукушкиному хешированию), так и компактность, поскольку сохраняются только цифровые отпечатки. Операции поиска и удаления просты. Существует максимум два местоположения, которые нужно проверить: <math>h_1(x)</math> и <math>h_2(x)</math>. Если элемент найден, соответствующая операция поиска или удаления может быть выполнена за время <math>O(1)</math>. Более подробный теоретический анализ кукушкиного фильтра можно найти в литературе[3][4].
Сравнение с фильтром Блума
Кукушкин фильтр похож на фильтр Блума тем, что они оба очень быстры и компактны, и оба они могут возвращать ложноположительные результаты:
- Оптимальные по памяти фильтры Блума используют <math>1{,}44\log_2(1/\varepsilon)</math> битов для каждого вставленного ключа, где <math>\varepsilon</math> — частота ложноположительных срабатываний. Кукушкину фильтру необходимо <math>(\log_2(1/\varepsilon) + 2)/\alpha</math>, где <math>\alpha</math> — коэффициент загрузки хеш-таблицы, который может быть равен <math>95{,}5\,\%</math> в зависимости от настроек. Отметим, что теоретическая нижняя граница требует <math>\log_2(1/\varepsilon)</math> битов для каждого элемента.
- При положительном результате поиска оптимальный по памяти фильтр Блума требует константное количество <math>\log_2(1/\varepsilon)</math> операций доступа к битовому массиву, в то время как кукушкин фильтр требует не более двух таких операций.
- У кукушкина фильтра снижается скорость вставки после достижения порогового значения нагрузки, когда рекомендуется расширить таблицу. В фильтр Блума можно продолжать вставлять новые элементы, обратной стороной чего является высокая частота ложных срабатываний до расширения.
Ограничения
- Из кукушкина фильтра можно удалять только те элементы, которые точно были вставлены ранее.
- Вставка может завершиться неудачей, и потребуется заново вычислять хеш. Амортизированная сложность вставки по-прежнему <math>O(1)</math>[5].
Примечания
Ссылки
