Зозулин фільтр

Зозулин фільтр (англ. cuckoo filter) — це імовірнісна структура даних, яка використовується для перевірки того, чи елемент належить до множини, подібно до фільтр Блума . Хибно позитивні збіги можливі, але не хибно негативні – іншими словами, запит повертає «можливо в наборі» або «безумовно не в наборі». Зозулин фільтр, дозволяє видаляти наявні елементи, що не можливо з використанням фільтра Блума. Крім того, для додатків, які зберігають багато елементів і орієнтовані на помірно низьку долю хибно-позитивних результатів, фільтри зозулі можуть досягти меншого використання пам'яті, ніж оптимізовані по пам'яті фільтри Блума.

Зозулині фільтри були вперше описані в 2014 році

Опис алгоритму

У фільтрі зозулі використовується $n$-канальна множинно-асоціативна хеш-таблиця на основі хешування зозулі для зберігання цифрових відбитків усіх елементів (кожна корзина хеш-таблиці може зберігати до $n$ записів).

Зокрема, два індекси потенційних корзин $i$ і $j$  в таблиці для певного елемента обчислюються за допомогою двох хеш-функцій (має назву хешування с частковим ключем, англ. partial-key cuckoo hashing) ):

$i=h_{1}(x)={\text{hash}}(x)$

$j=h_{2}(x)=h_{1}(x)\oplus {\text{hash}}({\text{fingerprint}}(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\%$ на основі налаштувань зозулиного фільтра. Варто зазначити, що теоретична нижня межа об'єму пам'яті складає $\log _{2}(1/\epsilon )$ бітів для кожного елемента.
• При позитивному пошуку оптимальний для пам'яті фільтр Блума вимагає константно $\log _{2}(1/\epsilon )$ операцій звернення до бітового масиву, тоді як зозулин фільтр потребує щонайбільше двох таких операції.
• Після досягнення порогового значення навантаження швидкість вставки до фільтра зозулі може деградувати. В такому випадку рекомендується розширення таблиці. Навпроти, фільтри Блума можуть продовжувати вставляти нові елементи без розширення таблиці, але це можливо ціною отримання вищого рівня хибно позитивних результатів.

Обмеження

• Зозулин фільтр може видаляти лише елементи, про які відомо, що вони були вставлені раніше.
• Вставка може бути невдалою, в такому випадку хешування потрібно проводити наново. Варто зазначити, що амортизована складність вставки залишається $O(1)$ .