Участник:Joparino/Кукушкин фильтр: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Кукушкин фильтр''' — это пространственно-эффективная [[Вероятность|вероятностная]] [[структура данных]], которая используется для проверки, является ли элемент членом [[Множество (тип данных)|множества]], как это делает [[Фильтр Блума]]. [[Ошибки первого и второго рода|Ложноположительные результаты]] возможны, но [[Ошибки первого и второго рода|ложноотрицательные результаты]] не возможны – другими словами, запрос возвращает либо "возможно в множестве" или "точно не в множестве". Кукушкин фильтр также может удалять существующие элементы, что не умеет фильтр Блума. В дополнении, для приложения, которые хранят много элементов и нацелены на умеренно низкие показатели ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат пространства, чем оптимизированный по пространству фильтр Блума.<ref>
'''Кукушкин фильтр''' — это пространственно-эффективная [[Вероятность|вероятностная]] [[структура данных]], которая используется для проверки, является ли элемент членом [[Множество (тип данных)|множества]], как это делает [[фильтр Блума]]. [[Ошибки первого и второго рода|Ложноположительные результаты]] возможны, но [[Ошибки первого и второго рода|ложноотрицательные результаты]] не возможны – другими словами, запрос возвращает либо "возможно в множестве" или "точно не в множестве". Кукушкин фильтр также может удалять существующие элементы, что не умеет фильтр Блума. В дополнении, для приложения, которые хранят много элементов и нацелены на умеренно низкие показатели ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат пространства, чем оптимизированный по пространству фильтр Блума.<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
Строка 27: Строка 27:
:<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>


Применение двух вышеуказанных хеш-функций для построения кукушкиных хеш-таблиц позволяет перемещать элементы только на основе отпечатков пальцев, когда извлечение исходного элемента невозможно. В результате при вставке нового элемента, который требует перемещения существующего элемента <math>y</math> другое возможное местоположение <math>j</math> в таблице для этого элемента <math>y</math> исключается из корзины <math>i</math> вычисляется по
Applying the above two hash functions
to construct a cuckoo hash table enables item relocation based only on fingerprints
when retrieving the original item is impossible.
As a result, when inserting a new item that requires relocating an existing item <math>y</math>,
the other possible location <math>j</math> in the table
for this item <math>y</math> kicked out from bucket <math>i</math> is calculated by


:<math>j = i\oplus\text{hash}(\text{fingerprint}(y))</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>
Based on partial-key cuckoo hashing, the hash table can achieve both highly-utilization (thanks to cuckoo hashing),
and compactness because only fingerprints are stored. Lookup and delete operations of a cuckoo filter are straightforward.
There are a maximum of two locations to check by <math>h_1(x)</math> and <math>h_2(x)</math>.
If found, the appropriate lookup or delete operation can be performed in <math>O(1)</math> time.
More theoretical analysis of cuckoo filters can be found in the literature.<ref>
{{cite conference
{{cite conference
| first = David | last = Eppstein | authorlink = David Eppstein
| first = David | last = Eppstein | authorlink = David Eppstein
Строка 61: Строка 52:
}}</ref>
}}</ref>


==Сравнение с фильтрами Блума==
==Comparison to Bloom filters==
Кукушкин фильтр похож на [[фильтр Блума]] в том, что они оба очень быстры и компактны, и оба они могут возвращать ложноположительные срабатывания в качестве ответов на запросы с заданным членством:
A cuckoo filter is similar to a [[Bloom filter]] in that they both are very fast and compact,
and they may both return false positives as answers to set-membership queries:


* Space-optimal Bloom filters use <math>1.44\log_2(1/\epsilon)</math> bits of space per inserted key, where <math>\epsilon</math> is the false positive rate. A cuckoo filter requires <math>(\log_2(1/\epsilon) + 2)/\alpha</math> where <math>\alpha</math> is the hash table load factor, which can be <math>95.5\%</math> based on the cuckoo filter's setting. Note that the information theoretical lower bound requires <math>\log_2(1/\epsilon)</math> bits for each item.
* Пространственно-оптимальные фильтры Блума используют <math>1.44\log_2(1/\epsilon)</math> биты для каждого вставленного ключа, где <math>\epsilon</math> — частота ложноположительных срабатываний. Кукушкину фильтру необходимо <math>(\log_2(1/\epsilon) + 2)/\alpha</math> где <math>\alpha</math> — является коэффициентом загрузки хэш-таблицы, который может быть <math>95.5\%</math> в зависимости от настройки кукушкиного фильтра. Отметим, что теоретическая нижняя граница информации требует <math>\log_2(1/\epsilon)</math> битов для каждого элемента.
* При положительном поиске, пространственно-оптимальный фильтр Блума требует постоянного <math>\log_2(1/\epsilon)</math> доступа к памяти в битовый массив, в то время как кукушкин фильтр требуется не более двух постоянных поисков.
* On a positive lookup, a space-optimal Bloom filter requires a constant <math>\log_2(1/\epsilon)</math> memory accesses into the bit array, whereas a cuckoo filter requires constant two lookups at most.
* Кукушкин фильтр снижает скорость вставки после достижения порогового значения нагрузки, когда рекомендуется расширять таблицу. В отличие от этого, фильтры Блума могут продолжать вставлять новые элементы за счет более высокой частоты ложных срабатываний перед расширением.
* Cuckoo filters have degraded insertion speed after reaching a load threshold, when table expanding is recommended. In contrast, Bloom filters can keep inserting new items at the cost of a higher false positive rate before expansion.


==Limitations==
==Limitations==

Версия от 16:40, 12 июля 2022

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

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

Алгоритм

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


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

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

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

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

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

Limitations

  • A cuckoo filter can only delete items that are known to be inserted before.
  • Insertion can fail and rehashing is required like other cuckoo hash tables. Note that the amortized insertion complexity is still .[5]

References

  1. ↑ Michael D. Mitzenmacher. Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters.
  2. ↑ 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.
  3. ↑ Eppstein, David (22 June 2016). 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) (ссылка)
  4. ↑ Fleming, Noah (17 May 2018). Cuckoo Hashing and Cuckoo Filters (PDF) (Technical report). University of Toronto.
  5. ↑ 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.
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Участник:Joparino/Кукушкин_фильтр&oldid=123982279