Кукушкин фильтр

Кукушкин фильтр (Шаблон:Lang-en) — это эффективная по памяти вероятностная структура данных, которая используется для проверки, принадлежит ли элемент множеству, подобно фильтру Блума. Возможны ложноположительные результаты, но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума.

Кукушкин фильтр впервые был описан в 2014 году.

Алгоритм

Кукушкин фильтр использует $n$-канальную множественно-ассоциативную хеш-таблицу, основанную на кукушкином хешировании, для хранения цифровых отпечатков всех элементов (в каждой корзине хеш-таблицы может храниться до $n$ записей). В частности, два индекса потенциальных корзин $i$ и $j$ в таблице для данного элемента $x$ вычисляются с помощью следующих двух хеш-функций (называется кукушкино хеширование с частичным ключом, Шаблон:Lang-en)):

$i=h_1(x)=\text{hash}(x)$

$j=h_2(x)=h_1(x)\oplus \text{hash}(\text{fingerprint}(x))$

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

$j=i\oplus \text{hash}(\text{fingerprint}(y))$

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

Сравнение с фильтром Блума

Кукушкин фильтр похож на фильтр Блума тем, что они оба очень быстры и компактны, и оба они могут возвращать ложноположительные результаты:

• Оптимальные по памяти фильтры Блума используют $1,44{\log }_2(1/\epsilon )$ битов для каждого вставленного ключа, где $\epsilon$ — частота ложноположительных срабатываний. Кукушкину фильтру необходимо $({\log }_2(1/\epsilon )+2)/\alpha$, где $\alpha$ — коэффициент загрузки хеш-таблицы, который может быть равен $95,5\mathrm{\%}$ в зависимости от настроек. Отметим, что теоретическая нижняя граница требует ${\log }_2(1/\epsilon )$ битов для каждого элемента.
• При положительном результате поиска оптимальный по памяти фильтр Блума требует константное количество ${\log }_2(1/\epsilon )$ операций доступа к битовому массиву, в то время как кукушкин фильтр требует не более двух таких операций.
• У кукушкина фильтра снижается скорость вставки после достижения порогового значения нагрузки, когда рекомендуется расширить таблицу. В фильтр Блума можно продолжать вставлять новые элементы, обратной стороной чего является высокая частота ложных срабатываний до расширения.

Ограничения

• Из кукушкина фильтра можно удалять только те элементы, которые точно были вставлены ранее.
• Вставка может завершиться неудачей, и потребуется заново вычислять хеш. Амортизированная сложность вставки по-прежнему $O(1)$.

Ссылки

• Probabilistic Filters By Example — A tutorial comparing Cuckoo and Bloom filters