Кукушкин фильтр: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Retimuko (обсуждение | вклад) стиль |
РобоСтася (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии 3 участников) | |||
Строка 1: | Строка 1: | ||
'''Кукушкин фильтр''' ({{lang-en|cuckoo filter}}) — это эффективная по памяти [[вероятность|вероятностная]] [[структура данных]], которая используется для проверки, принадлежит ли элемент [[множество (тип данных)|множеству]], подобно [[фильтр Блума|фильтру Блума]]. Возможны [[ошибки первого и второго рода|ложноположительные результаты]], но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума<ref> |
'''Кукушкин фильтр''' ({{lang-en|cuckoo filter}}) — это эффективная по памяти [[вероятность|вероятностная]] [[структура данных]], которая используется для проверки, принадлежит ли элемент [[множество (тип данных)|множеству]], подобно [[фильтр Блума|фильтру Блума]]. Возможны [[ошибки первого и второго рода|ложноположительные результаты]], но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума<ref>{{Cite web |
||
{{Cite web |
|||
| title = Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters |
| title = Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters |
||
| url = https://smartech.gatech.edu/handle/1853/60577 |
| url = https://smartech.gatech.edu/handle/1853/60577 |
||
| author = Michael D. Mitzenmacher |
| author = Michael D. Mitzenmacher |
||
| access-date = 2022-07-15 |
|||
| archive-date = 2022-06-26 |
|||
| archive-url = https://web.archive.org/web/20220626084927/https://smartech.gatech.edu/handle/1853/60577 |
|||
| deadlink = no |
|||
}}</ref>. |
}}</ref>. |
||
Строка 24: | Строка 27: | ||
Кукушкин фильтр использует <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> вычисляются с помощью следующих двух хеш-функций (называется ''кукушкино хеширование с частичным ключом'', {{lang-en|partial-key cuckoo hashing}})<ref name="CuckooFilter" />): |
||
: <math>i = h_1(x)=\text{hash}(x)</math |
: <math>i = h_1(x)=\text{hash}(x)</math> |
||
: <math>j = h_2(x)=h_1(x)\oplus\text{hash}(\text{fingerprint}(x))</math> |
: <math>j = h_2(x)=h_1(x)\oplus\text{hash}(\text{fingerprint}(x))</math> |
||
Строка 36: | Строка 39: | ||
| title = Cuckoo filter: Simplification and analysis |
| title = Cuckoo filter: Simplification and analysis |
||
| conference = Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) |
| conference = Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) |
||
| date |
| date=2016-06-22 |
||
| location = Reykjavik, Iceland |
| location = Reykjavik, Iceland |
||
| pages = 8:1–8:12 |
| pages = 8:1–8:12 |
||
Строка 43: | Строка 46: | ||
| doi = 10.4230/LIPIcs.SWAT.2016.8 |
| doi = 10.4230/LIPIcs.SWAT.2016.8 |
||
| arxiv = 1604.06067 |
| arxiv = 1604.06067 |
||
}}</ref><ref> |
}}</ref><ref>{{cite techreport |
||
| first = Noah |
|||
{{cite techreport |
|||
| last = Fleming |
|||
| url = http://www.cs.toronto.edu/~noahfleming/CuckooHashing.pdf |
| url = http://www.cs.toronto.edu/~noahfleming/CuckooHashing.pdf |
||
| title = Cuckoo Hashing and Cuckoo Filters |
| title = Cuckoo Hashing and Cuckoo Filters |
||
| date |
| date=2018-05-17 |
||
| publisher = University of Toronto |
| publisher = University of Toronto |
||
| access-date = 2022-07-15 |
|||
| archive-date = 2022-08-13 |
|||
| archive-url = https://web.archive.org/web/20220813205001/https://www.cs.toronto.edu/~noahfleming/CuckooHashing.pdf |
|||
| url-status = live |
|||
}}</ref>. |
}}</ref>. |
||
Строка 63: | Строка 70: | ||
* Вставка может завершиться неудачей, и потребуется заново вычислять хеш. Амортизированная сложность вставки по-прежнему <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>. |
* Вставка может завершиться неудачей, и потребуется заново вычислять хеш. Амортизированная сложность вставки по-прежнему <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>. |
||
== |
== Примечания == |
||
{{примечания}} |
{{примечания}} |
||
Текущая версия от 02:04, 25 июля 2024
Кукушкин фильтр (англ. cuckoo filter) — это эффективная по памяти вероятностная структура данных, которая используется для проверки, принадлежит ли элемент множеству, подобно фильтру Блума. Возможны ложноположительные результаты, но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума (если не использовать вариант с подсчётом, требующий больше памяти). В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума[1].
Кукушкин фильтр впервые был описан в 2014 году[2].
Алгоритм
[править | править код]Кукушкин фильтр использует -канальную множественно-ассоциативную хеш-таблицу, основанную на кукушкином хешировании, для хранения цифровых отпечатков всех элементов (в каждой корзине хеш-таблицы может храниться до записей). В частности, два индекса потенциальных корзин и в таблице для данного элемента вычисляются с помощью следующих двух хеш-функций (называется кукушкино хеширование с частичным ключом, англ. partial-key cuckoo hashing)[2]):
Применение двух вышеуказанных хеш-функций для построения кукушкиных хеш-таблиц позволяет перемещать элементы только на основе цифрового отпечатка, когда узнать исходный элемент невозможно. В результате при вставке нового элемента, который требует перемещения существующего элемента , другое возможное местоположение в таблице для элемента , вытесненного из корзины вычисляется по формуле
Основанная на кукушкином хешировании с частичным ключом хеш-таблица может обеспечить как высокую степень использования (благодаря кукушкиному хешированию), так и компактность, поскольку сохраняются только цифровые отпечатки. Операции поиска и удаления просты. Существует максимум два местоположения, которые нужно проверить: и . Если элемент найден, соответствующая операция поиска или удаления может быть выполнена за время . Более подробный теоретический анализ кукушкиного фильтра можно найти в литературе[3][4].
Сравнение с фильтром Блума
[править | править код]Кукушкин фильтр похож на фильтр Блума тем, что они оба очень быстры и компактны, и оба они могут возвращать ложноположительные результаты:
- Оптимальные по памяти фильтры Блума используют битов для каждого вставленного ключа, где — частота ложноположительных срабатываний. Кукушкину фильтру необходимо , где — коэффициент загрузки хеш-таблицы, который может быть равен в зависимости от настроек. Отметим, что теоретическая нижняя граница требует битов для каждого элемента.
- При положительном результате поиска оптимальный по памяти фильтр Блума требует константное количество операций доступа к битовому массиву, в то время как кукушкин фильтр требует не более двух таких операций.
- У кукушкина фильтра снижается скорость вставки после достижения порогового значения нагрузки, когда рекомендуется расширить таблицу. В фильтр Блума можно продолжать вставлять новые элементы, обратной стороной чего является высокая частота ложных срабатываний до расширения.
Ограничения
[править | править код]- Из кукушкина фильтра можно удалять только те элементы, которые точно были вставлены ранее.
- Вставка может завершиться неудачей, и потребуется заново вычислять хеш. Амортизированная сложность вставки по-прежнему [5].
Примечания
[править | править код]- ↑ Michael D. Mitzenmacher. Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters . Дата обращения: 15 июля 2022. Архивировано 26 июня 2022 года.
- ↑ 1 2 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: Practically better than Bloom. Proc. 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT '14). Sydney, Australia. pp. 75—88. doi:10.1145/2674005.2674994. ISBN 9781450332798.
- ↑
Eppstein, David (2016-06-22). Cuckoo filter: Simplification and analysis. Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 53. Reykjavik, Iceland. pp. 8:1–8:12. arXiv:1604.06067. doi:10.4230/LIPIcs.SWAT.2016.8.
{{cite conference}}
: Википедия:Обслуживание CS1 (не помеченный открытым DOI) (ссылка) - ↑ Fleming, Noah (2018-05-17). Cuckoo Hashing and Cuckoo Filters (PDF) (Technical report). University of Toronto. Архивировано (PDF) 13 августа 2022. Дата обращения: 15 июля 2022.
- ↑ Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo hashing". Proc. 9th Annual European Symposium on Algorithms (ESA 2001). Lecture Notes in Computer Science. Vol. 2161. Århus, Denmark. pp. 121—133. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.