Кукушкин фильтр
Кукушкин фильтр (англ. 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.