Кукушечный фильтр - Cuckoo filter

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

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

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

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

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

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

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

${ displaystyle j = я oplus { text {hash}} ({ text {fingerprint}} (y))}$

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

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

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

• Использование оптимальных по пространству фильтров Блума ${ displaystyle 1.44 log _ {2} (1 / epsilon)}$ бит пространства на вставленный ключ, где ${ displaystyle epsilon}$ - коэффициент ложных срабатываний. Фильтр с кукушкой требует ${ Displaystyle ( журнал _ {2} (1 / эпсилон) +2) / альфа}$ куда ${ displaystyle alpha}$ коэффициент загрузки хэш-таблицы, который может быть ${ displaystyle 95,5 \%}$ на основе настройки фильтра кукушки. Обратите внимание, что теоретическая нижняя граница информации требует ${ Displaystyle журнал _ {2} (1 / epsilon)}$ бит для каждого элемента.
• При положительном поиске для оптимального по пространству фильтра Блума требуется постоянная ${ Displaystyle журнал _ {2} (1 / epsilon)}$ память обращается к битовому массиву, тогда как фильтр с кукушкой требует постоянных двух поисков максимум.
• Фильтры с кукушкой снизили скорость вставки после достижения порога загрузки, когда рекомендуется расширение таблицы. Напротив, фильтры Блума могут продолжать вставлять новые элементы за счет более высокого процента ложных срабатываний перед расширением.

Ограничения

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

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

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

• Вероятностные фильтры на примере - учебное пособие по сравнению фильтров кукушки и Блума.