Кукушкин фильтр - История изменений

Patarakin в 07:59, 19 октября 2022

2022-10-19T07:59:54Z

@@ Строка 1: / Строка 1: @@
-'''Кукушкин фильтр''' ({{lang-en|cuckoo filter}}) — это эффективная по памяти [[вероятность|вероятностная]] [[структура данных]], которая используется для проверки, принадлежит ли элемент [[множество (тип данных)|множеству]], подобно [[фильтр Блума|фильтру Блума]]. Возможны [[ошибки первого и второго рода|ложноположительные результаты]], но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума<ref>
+'''Кукушкин фильтр'''— это эффективная по памяти [[вероятность|вероятностная]] [[структура данных]], которая используется для проверки, принадлежит ли элемент [[множество (тип данных)|множеству]]. Возможны [[ошибки первого и второго рода|ложноположительные результаты]], но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума
 == Алгоритм ==
-Кукушкин фильтр использует <math>n</math>-канальную множественно-ассоциативную хеш-таблицу, основанную на [[кукушкино хеширование|кукушкином хешировании]], для хранения [[цифровые отпечатки|цифровых отпечатков]] всех элементов (в каждой корзине хеш-таблицы может храниться до <math>n</math> записей). В частности, два индекса потенциальных корзин <math>i</math> и <math>j</math> в таблице для данного элемента <math>x</math> вычисляются с помощью следующих двух хеш-функций (называется ''кукушкино хеширование с частичным ключом'', {{lang-en|partial-key cuckoo hashing}})<ref name="CuckooFilter" />):
+Кукушкин фильтр использует <math>n</math>-канальную множественно-ассоциативную хеш-таблицу, основанную на [[кукушкино хеширование|кукушкином хешировании]], для хранения [[цифровые отпечатки|цифровых отпечатков]] всех элементов (в каждой корзине хеш-таблицы может храниться до <math>n</math> записей). В частности, два индекса потенциальных корзин <math>i</math> и <math>j</math> в таблице для данного элемента <math>x</math> вычисляются с помощью следующих двух хеш-функций (называется ''кукушкино хеширование с частичным ключом''):
 : <math>i = h_1(x)=\text{hash}(x)</math><br>
@@ Строка 32: / Строка 11: @@
 Основанная на кукушкином хешировании с частичным ключом хеш-таблица может обеспечить как высокую степень использования (благодаря кукушкиному хешированию), так и компактность, поскольку сохраняются только цифровые отпечатки. Операции поиска и удаления просты. Существует максимум два местоположения, которые нужно проверить: <math>h_1(x)</math> и <math>h_2(x)</math>. Если элемент найден, соответствующая операция поиска или удаления может быть выполнена за время <math>O(1)</math>. Более подробный теоретический анализ кукушкиного фильтра можно найти в литературе<ref>
-{{cite conference
 == Сравнение с фильтром Блума ==
@@ Строка 59: / Строка 20: @@
 * У кукушкина фильтра снижается скорость вставки после достижения порогового значения нагрузки, когда рекомендуется расширить таблицу. В фильтр Блума можно продолжать вставлять новые элементы, обратной стороной чего является высокая частота ложных срабатываний до расширения.
 [[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:54Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Retimuko: стиль

2022-07-17T06:02:43Z

стиль

Новая страница

'''Кукушкин фильтр''' ({{lang-en|cuckoo filter}}) — это эффективная по памяти [[вероятность|вероятностная]] [[структура данных]], которая используется для проверки, принадлежит ли элемент [[множество (тип данных)|множеству]], подобно [[фильтр Блума|фильтру Блума]]. Возможны [[ошибки первого и второго рода|ложноположительные результаты]], но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума<ref>
{{Cite web
| title = Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters
| url = https://smartech.gatech.edu/handle/1853/60577
| author = Michael D. Mitzenmacher
}}</ref>.

Кукушкин фильтр впервые был описан в 2014 году<ref name="CuckooFilter">
{{cite conference
| last1 = Fan | first1 = Bin
| last2 = Andersen | first2 = Dave G.
| last3 = Kaminsky | first3 = Michael
| last4 = Mitzenmacher | first4 = Michael D.
| title = Cuckoo filter: Practically better than Bloom
| doi = 10.1145/2674005.2674994
| pages = 75–88
| conference = Proc. 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT '14)
| location = Sydney, Australia
| year = 2014| isbn = 9781450332798
| doi-access = free
}}</ref>.

== Алгоритм ==
Кукушкин фильтр использует <math>n</math>-канальную множественно-ассоциативную хеш-таблицу, основанную на [[кукушкино хеширование|кукушкином хешировании]], для хранения [[цифровые отпечатки|цифровых отпечатков]] всех элементов (в каждой корзине хеш-таблицы может храниться до <math>n</math> записей). В частности, два индекса потенциальных корзин <math>i</math> и <math>j</math> в таблице для данного элемента <math>x</math> вычисляются с помощью следующих двух хеш-функций (называется ''кукушкино хеширование с частичным ключом'', {{lang-en|partial-key cuckoo hashing}})<ref name="CuckooFilter" />):

: <math>i = h_1(x)=\text{hash}(x)</math><br>
: <math>j = h_2(x)=h_1(x)\oplus\text{hash}(\text{fingerprint}(x))</math>

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

: <math>j = i\oplus\text{hash}(\text{fingerprint}(y))</math>

Основанная на кукушкином хешировании с частичным ключом хеш-таблица может обеспечить как высокую степень использования (благодаря кукушкиному хешированию), так и компактность, поскольку сохраняются только цифровые отпечатки. Операции поиска и удаления просты. Существует максимум два местоположения, которые нужно проверить: <math>h_1(x)</math> и <math>h_2(x)</math>. Если элемент найден, соответствующая операция поиска или удаления может быть выполнена за время <math>O(1)</math>. Более подробный теоретический анализ кукушкиного фильтра можно найти в литературе<ref>
{{cite conference
| first = David | last = Eppstein
| title = Cuckoo filter: Simplification and analysis
| conference = Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
| date = 22 June 2016
| location = Reykjavik, Iceland
| pages = 8:1–8:12
| series = Leibniz International Proceedings in Informatics (LIPIcs)
| volume = 53
| doi = 10.4230/LIPIcs.SWAT.2016.8
| arxiv = 1604.06067
}}</ref><ref>
{{cite techreport
| first = Noah | last = Fleming
| url = http://www.cs.toronto.edu/~noahfleming/CuckooHashing.pdf
| title = Cuckoo Hashing and Cuckoo Filters
| date = 17 May 2018
| publisher = University of Toronto
}}</ref>.

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

* Оптимальные по памяти фильтры Блума используют <math>1{,}44\log_2(1/\varepsilon)</math> битов для каждого вставленного ключа, где <math>\varepsilon</math> — частота ложноположительных срабатываний. Кукушкину фильтру необходимо <math>(\log_2(1/\varepsilon) + 2)/\alpha</math>, где <math>\alpha</math> — коэффициент загрузки хеш-таблицы, который может быть равен <math>95{,}5\,\%</math> в зависимости от настроек. Отметим, что теоретическая нижняя граница требует <math>\log_2(1/\varepsilon)</math> битов для каждого элемента.
* При положительном результате поиска оптимальный по памяти фильтр Блума требует константное количество <math>\log_2(1/\varepsilon)</math> операций доступа к битовому массиву, в то время как кукушкин фильтр требует не более двух таких операций.
* У кукушкина фильтра снижается скорость вставки после достижения порогового значения нагрузки, когда рекомендуется расширить таблицу. В фильтр Блума можно продолжать вставлять новые элементы, обратной стороной чего является высокая частота ложных срабатываний до расширения.

== Ограничения ==
* Из кукушкина фильтра можно удалять только те элементы, которые точно были вставлены ранее.
* Вставка может завершиться неудачей, и потребуется заново вычислять хеш. Амортизированная сложность вставки по-прежнему <math>O(1)</math><ref name="CuckooHashing">{{Cite conference | last1 = Pagh | first1 = Rasmus | last2 = Rodler | first2 = Flemming Friche| chapter = Cuckoo hashing| doi = 10.1007/3-540-44676-1_10 | title = Proc. 9th Annual European Symposium on Algorithms (ESA 2001) | series = Lecture Notes in Computer Science | volume = 2161 | pages = 121–133| year = 2001 | isbn = 978-3-540-42493-2 | location = Århus, Denmark}}</ref>.

== Ссылки ==
{{примечания}}

== Ссылки ==
* [https://bdupras.github.io/filter-tutorial/ Probabilistic Filters By Example — A tutorial comparing Cuckoo and Bloom filters]

[[Категория:Алгоритмы сжатия с потерями]]
[[Категория:Структуры данных]]