Участник:Joparino/Кукушкин фильтр

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

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

Алгоритм

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

$i=h_{1}(x)={\text{hash}}(x)$

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

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 $y$, the other possible location $j$ in the table for this item $y$ kicked out from bucket $i$ is calculated by

$j=i\oplus {\text{hash}}({\text{fingerprint}}(y))$

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 $h_{1}(x)$ and $h_{2}(x)$. If found, the appropriate lookup or delete operation can be performed in $O(1)$ time. More theoretical analysis of cuckoo filters can be found in the literature.

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 $1.44\log _{2}(1/\epsilon )$ bits of space per inserted key, where $\epsilon$ is the false positive rate. A cuckoo filter requires $(\log _{2}(1/\epsilon )+2)/\alpha$ where $\alpha$ is the hash table load factor, which can be $95.5\%$ based on the cuckoo filter's setting. Note that the information theoretical lower bound requires $\log _{2}(1/\epsilon )$ bits for each item.
• On a positive lookup, a space-optimal Bloom filter requires a constant $\log _{2}(1/\epsilon )$ 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

• 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 $O(1)$.

External links

• Probabilistic Filters By Example – A tutorial comparing Cuckoo and Bloom filters.