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

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

Алгоритм

Кукушкин фильтр использует [math]\displaystyle{ n }[/math]-канальную множественно-ассоциативную хеш-таблицу, основанную на кукушкином хешировании, для хранения цифровых отпечатков всех элементов (в каждой корзине хеш-таблицы может храниться до [math]\displaystyle{ n }[/math] записей). В частности, два индекса потенциальных корзин [math]\displaystyle{ i }[/math] и [math]\displaystyle{ j }[/math] в таблице для данного элемента [math]\displaystyle{ x }[/math] вычисляются с помощью следующих двух хеш-функций (называется кукушкино хеширование с частичным ключом):

[math]\displaystyle{ i = h_1(x)=\text{hash}(x) }[/math]

[math]\displaystyle{ j = h_2(x)=h_1(x)\oplus\text{hash}(\text{fingerprint}(x)) }[/math]

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

[math]\displaystyle{ j = i\oplus\text{hash}(\text{fingerprint}(y)) }[/math]

Основанная на кукушкином хешировании с частичным ключом хеш-таблица может обеспечить как высокую степень использования (благодаря кукушкиному хешированию), так и компактность, поскольку сохраняются только цифровые отпечатки. Операции поиска и удаления просты. Существует максимум два местоположения, которые нужно проверить: [math]\displaystyle{ h_1(x) }[/math] и [math]\displaystyle{ h_2(x) }[/math]. Если элемент найден, соответствующая операция поиска или удаления может быть выполнена за время [math]\displaystyle{ O(1) }[/math]. Более подробный теоретический анализ кукушкиного фильтра можно найти в литературе<ref>

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

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

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