WikiDer > Кукушечный фильтр

Cuckoo filter

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

Впервые фильтры с кукушкой были описаны в 2014 году.[2]

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

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


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

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

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

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

  • Использование оптимальных по пространству фильтров Блума бит пространства на вставленный ключ, где - коэффициент ложных срабатываний. Фильтр с кукушкой требует куда коэффициент загрузки хэш-таблицы, который может быть на основе настройки фильтра кукушки. Обратите внимание, что теоретическая нижняя граница информации требует бит для каждого элемента.
  • При положительном поиске для оптимального по пространству фильтра Блума требуется постоянная память обращается к битовому массиву, тогда как фильтр с кукушкой требует постоянных двух поисков максимум.
  • Фильтры с кукушкой снизили скорость вставки после достижения порога загрузки, когда рекомендуется расширение таблицы. Напротив, фильтры Блума могут продолжать вставлять новые элементы за счет более высокого процента ложных срабатываний перед расширением.

Ограничения

  • Фильтр с кукушкой может удалять только те элементы, о которых известно, что они были вставлены ранее.
  • Вставка может завершиться неудачно, и потребуется повторное хеширование, как и другие хеш-таблицы с кукушкой. Обратите внимание, что амортизированная сложность вставки по-прежнему .[5]

Рекомендации

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

внешняя ссылка