Фильтр «Кукушка»

Структура данных для приблизительного членства в наборе

Фильтр кукушки — это вероятностная структура данных , которая эффективно использует пространство , чтобы проверить, является ли элемент членом множества , как это делает фильтр Блума . Ложные положительные совпадения возможны, но ложные отрицательные — нет, другими словами, запрос возвращает либо «возможно в множестве», либо «определенно не в множестве». Фильтр кукушки также может удалять существующие элементы, что не поддерживается фильтрами Блума. Кроме того, для приложений, которые хранят много элементов и нацелены на умеренно низкие показатели ложных положительных срабатываний, фильтры кукушки могут достичь меньших накладных расходов по пространству, чем оптимизированные по пространству фильтры Блума. ^[1]

Фильтры «кукушка» были впервые описаны в 2014 году. ^[2]

Описание алгоритма

Фильтр кукушки использует хэш-таблицу на основе хэширования кукушки для хранения отпечатков элементов. ^[2] Структура данных разбита на блоки определенного размера . Чтобы вставить отпечаток элемента , сначала вычисляются два потенциальных блока и то, куда можно вставить. Эти блоки вычисляются с использованием формулы ${\displaystyle b}$ ${\displaystyle x}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle h_{2}(x)}$ ${\displaystyle x}$

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

${\displaystyle h_{2}(x)=h_{1}(x)\oplus {\text{hash}}({\text{fingerprint}}(x))}$

Обратите внимание, что благодаря симметрии операции XOR можно вычислить из , и из . Как определено выше, ; следует, что . Именно эти свойства позволяют хранить отпечатки пальцев с помощью хеширования кукушки. ${\displaystyle h_{2}(x)}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle h_{2}(x)}$ ${\displaystyle h_{2}(x)=h_{1}(x)\oplus {\text{hash}}({\text{fingerprint}}(x))}$ ${\displaystyle h_{1}(x)=h_{2}(x)\oplus {\text{hash}}({\text{fingerprint}}(x))}$

Отпечаток пальца помещается в один из бакетов и . Если бакеты заполнены, то один из отпечатков пальцев в бакете вытесняется с помощью хеширования кукушки и помещается в другой бакет, куда он может попасть. Если этот бакет, в свою очередь, также заполнен, то это может вызвать еще одно вытеснение и т. д. ${\displaystyle x}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle h_{2}(x)}$

Таблица хэшей может достигать как высокой утилизации (благодаря хэшированию кукушки ), так и компактности, поскольку сохраняются только отпечатки пальцев. Операции поиска и удаления фильтра кукушки просты. ^[2]

Максимум два бакета для проверки и . Если найдено, соответствующая операция поиска или удаления может быть выполнена вовремя . Часто на практике является константой. ${\displaystyle h_{1}(x)}$ ${\displaystyle h_{2}(x)}$ ${\displaystyle O(b)}$ ${\displaystyle b}$

Для того чтобы хэш-таблица могла предоставить теоретические гарантии, размер отпечатка должен быть не менее бит. ^{[2] [3] [4]} При соблюдении этого ограничения фильтры кукушки гарантируют частоту ложных срабатываний не более . ^[2] ${\displaystyle f}$ ${\displaystyle \Omega ((\log n)/b)}$ ${\displaystyle \epsilon \leq b/2^{f-1}}$

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

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

• Оптимальные по пространству фильтры Блума используют биты пространства на вставленный ключ, где — частота ложных срабатываний. Фильтр кукушки требует пространства на ключ ^[2], где — коэффициент загрузки хэш-таблицы, который может быть основан на настройке фильтра кукушки. Обратите внимание, что нижняя теоретическая граница информации требует биты для каждого элемента. Как фильтры Блума, так и фильтры кукушки с низкой нагрузкой могут быть сжаты, когда не используются. ${\displaystyle 1.44\log _{2}(1/\epsilon )}$ ${\displaystyle \epsilon }$ ${\displaystyle (\log _{2}(1/\epsilon )+1+\log _{2}b)/\alpha }$ ${\displaystyle \alpha }$ ${\displaystyle 95.5\%}$ ${\displaystyle \log _{2}(1/\epsilon )}$
• При положительном поиске оптимальный по пространству фильтр Блума требует постоянного числа обращений к памяти в битовом массиве, тогда как фильтр «кукушка» требует максимум числа обращений к памяти, что на практике может быть константой. ${\displaystyle \log _{2}(1/\epsilon )}$ ${\displaystyle 2b}$
• Фильтры Cuckoo снижают скорость вставки после достижения порога нагрузки, когда рекомендуется расширение таблицы. Напротив, фильтры Bloom могут продолжать вставлять новые элементы ценой более высокого уровня ложных срабатываний перед расширением.
• Фильтры Блума предлагают быстрые операции объединения и приблизительного пересечения с использованием дешевых побитовых операций, которые также можно применять к сжатым фильтрам Блума, если используется потоковое сжатие.

Ограничения

• Фильтр «кукушка» может удалять только те элементы, которые, как известно, были вставлены ранее.
• Вставка может не сработать, и требуется повторное хеширование, как и в других хеш-таблицах Cuckoo. Обратите внимание, что амортизированная сложность вставки все еще . ^[5] ${\displaystyle O(1)}$
• Фильтры Cuckoo требуют размер отпечатка пальца не менее бит. Это означает, что пространство на ключ должно быть не менее бит, даже если оно большое. На практике выбирается достаточно большим, чтобы это не было серьезной проблемой. ^[2] ${\displaystyle f}$ ${\displaystyle \Omega ((\log n)/b)}$ ${\displaystyle \Omega ((\log n)/b)}$ ${\displaystyle \epsilon }$ ${\displaystyle b}$

Ссылки

• Портал компьютерного программирования

1. Майкл Д. Митценмахер . «Фильтры Блума, хеширование Cuckoo, фильтры Cuckoo, адаптивные фильтры Cuckoo и обученные фильтры Блума».
2. Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Фильтр Cuckoo: Практически лучше, чем Bloom . Proc. 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT '14). Сидней, Австралия. стр. 75–88. doi : 10.1145/2674005.2674994 . ISBN 9781450332798.
3. Эппштейн, Дэвид (22 июня 2016 г.). Фильтр кукушки: упрощение и анализ . Труды 15-го Скандинавского симпозиума и семинаров по теории алгоритмов (SWAT 2016). Международные труды им. Лейбница по информатике (LIPIcs). Том 53. Рейкьявик, Исландия. С. 8:1–8:12. arXiv : 1604.06067 . doi : 10.4230/LIPIcs.SWAT.2016.8 .
4. Флеминг, Ноа (17 мая 2018 г.). Cuckoo Hashing и Cuckoo Filters (PDF) (Технический отчет). Университет Торонто.
5. Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка-хеширование». Учеб. 9-й ежегодный европейский симпозиум по алгоритмам (ESA 2001) . Конспекты лекций по информатике. Том. 2161. Орхус, Дания. стр. 121–133. дои : 10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.

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

• Вероятностные фильтры на примерах – Учебное пособие, сравнивающее фильтры Кукушки и Блума.