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

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

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

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

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

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

$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/ϵ)$ біт місця для кожного вставленого ключа, де $ϵ$ це коефіцієнт хибно позитивних результатів. Зозулиному фільтру необхідно $({\log }_2(1/ϵ)+2)/\alpha$ де $\alpha$ це коефіцієнт завантаження хеш-таблиці, який може бути $95.5\mathrm{\%}$ на основі налаштувань зозулиного фільтра. Варто зазначити, що теоретична нижня межа об'єму пам'яті складає ${\log }_2(1/ϵ)$ бітів для кожного елемента.
• При позитивному пошуку оптимальний для пам'яті фільтр Блума вимагає константно ${\log }_2(1/ϵ)$ операцій звернення до бітового масиву, тоді як зозулин фільтр потребує щонайбільше двох таких операції.
• Після досягнення порогового значення навантаження швидкість вставки до фільтра зозулі може деградувати. В такому випадку рекомендується розширення таблиці. Навпроти, фільтри Блума можуть продовжувати вставляти нові елементи без розширення таблиці, але це можливо ціною отримання вищого рівня хибно позитивних результатів.

Обмеження

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