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

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

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

Алгоритм

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

$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)$.

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

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

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