Фильтр с кукушкой

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

Ссылки

^ Майкл Д. Митценмахер . «Фильтры Блума, хеширование кукушки, фильтры кукушки, адаптивные фильтры кукушки и изученные фильтры Блума» .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Фан, Бин; Андерсен, Дэйв Г.; Каминский, Майкл; Митценмахер, Майкл Д. (2014). Фильтр «Кукушка»: Практически лучше, чем Bloom . Учеб. 10-я Международная конференция ACM по новым сетевым экспериментам и технологиям (CoNEXT '14). Сидней, Австралия. стр. 75–88. дои : 10.1145/2674005.2674994 . ISBN 9781450332798 .
^ Эппштейн, Дэвид (22 июня 2016 г.). Фильтр «Кукушка»: Упрощение и анализ . Учеб. 15-й Скандинавский симпозиум и семинары по теории алгоритмов (SWAT 2016). Международные труды Лейбница по информатике (LIPIcs). Том. 53. Рейкьявик, Исландия. стр. 8:1–8:12. arXiv : 1604.06067 . doi : 10.4230/LIPIcs.SWAT.2016.8 .
^ Флеминг, Ной (17 мая 2018 г.). Хеширование Cuckoo и фильтры Cuckoo (PDF) (Технический отчет). Университет Торонто.
^ Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка». Учеб. 9-й ежегодный европейский симпозиум по алгоритмам (ESA 2001) . Конспекты лекций по информатике. Том. 2161. Орхус, Дания. стр. 121–133. дои : 10.1007/3-540-44676-1_10 . ISBN 978-3-540-42493-2 .

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

Вероятностные фильтры на примере — учебное пособие по сравнению фильтров Cuckoo и Bloom.

[1] Майкл Д. Митценмахер . «Фильтры Блума, хеширование кукушки, фильтры кукушки, адаптивные фильтры кукушки и изученные фильтры Блума» .

[CuckooFilter-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Фан, Бин; Андерсен, Дэйв Г.; Каминский, Майкл; Митценмахер, Майкл Д. (2014). Фильтр «Кукушка»: Практически лучше, чем Bloom . Учеб. 10-я Международная конференция ACM по новым сетевым экспериментам и технологиям (CoNEXT '14). Сидней, Австралия. стр. 75–88. дои : 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 и фильтры Cuckoo (PDF) (Технический отчет). Университет Торонто.

[CuckooHashing-5] Паг, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка». Учеб. 9-й ежегодный европейский симпозиум по алгоритмам (ESA 2001) . Конспекты лекций по информатике. Том. 2161. Орхус, Дания. стр. 121–133. дои : 10.1007/3-540-44676-1_10 . ISBN 978-3-540-42493-2 .

[1]

[2]

[3]

[4]

[5]