README
¶
Cuckoo
Package cuckoo implements a cuckoo filter using the techniques described in https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf.
Cuckoo filters are space-efficient, probabalistic structures for set membership tests. Essentially, a Cuckoo filter behaves like a set, but the only query it supports is "is x a member of the set?", to which it can only respond "no" or "maybe".
This is useful for many purposes, but one use case is avoiding expensive lookups. A Cuckoo filter of the items contained in the store is capable of definitively saying that an item is not in the store, and a lookup can be skipped entirely.
The rate at which the filter responds "maybe" when an item wasn't actually added to the filter is configurable, and changes the space used by the filter. If too many items are added to a filter, it overflows and returns "maybe" for every query, becoming useless.
Cuckoo filters are similar to Bloom filters, a more well-known variety of set-membership filter. However, Cuckoo filters have two main advantages:
-
For false positive rates below about 3%, Cuckoo filters use less space than a corresponding Bloom filter.
-
Cuckoo filters support Delete(), and Bloom filters do not.
Documentation
¶
Overview ¶
Package cuckoo implements a cuckoo filter using the techniques described in https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf.
Cuckoo filters are space-efficient, probabalistic structures for set membership tests. Essentially, a Cuckoo filter behaves like a set, but the only query it supports is "is x a member of the set?", to which it can only respond "no" or "maybe".
This is useful for many purposes, but one use case is avoiding expensive lookups. A Cuckoo filter of the items contained in the store is capable of definitively saying that an item is not in the store, and a lookup can be skipped entirely.
The rate at which the filter responds "maybe" when an item wasn't actually added to the filter is configurable, and changes the space used by the filter. If too many items are added to a filter, it overflows and returns "maybe" for every query, becoming useless.
Cuckoo filters are similar to Bloom filters, a more well-known variety of set-membership filter. However, Cuckoo filters have two main advantages:
- For false positive rates below about 3%, Cuckoo filters use less space than a corresponding Bloom filter.
- Cuckoo filters support Delete(), and Bloom filters do not.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
func New ¶
Returns a new filter capable of holding n items with an estimated false-positive rate of fp. If more than n items are added, the false-positive rate approaches 1.
func NewRaw ¶
Returns a new filter constructed using raw parameters.
- f: fingerprint length in bits. [2, 16]
- b: bucket size in number of entries. [1, 8]
- n: number of buckets in the table.
f * b must be less than 64.
The most efficient representation can be used when f=4 and b=4, using the fewest bits per item.
See https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf for more information on how to select these parameters.
func (*Filter) Contains ¶
Returns No if x is definitely not in the filter, and Maybe if x might be in the filter.
func (*Filter) Overflowed ¶
True if the filter has overflowed, and now blindly returns Maybe for every query. This happens when an Add() fails because there is no more room left in the filter.
Source Files