Участник:Joparino/Кукушкин фильтр

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

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

Алгоритм

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

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

Ограничения

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

Внешние ссылки

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

Категория: Алгоритмы сжатия с потерями