- Notifications
You must be signed in to change notification settings - Fork4
Cuckoo Filter: Practically better than bloom filter
License
vedhavyas/cuckoo-filter
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Practically better than Bloom Filter. Cuckoo filters support adding and removing items dynamically while achieving even higher performance than Bloom filters. For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters. It is a compact variant of a cuckoo hashtable that stores only fingerprints—a bit string derived from the item using a hash function—for each item inserted, instead of key-value pairs. The filter is densely filled with fingerprints (e.g., 95% entries occupied), which confers high space efficiency.
Paper can be foundhere.
--import "github.com/vedhavyas/cuckoo-filter"
typeFilterstruct {}
Filter is the cuckoo-filter
funcNewFilter(countuint32)*Filter
funcStdFilter()*Filter
StdFilter returns Standard Cuckoo-Filter
func (f*Filter)Count()uint32
Count returns total inserted items into filter
func (f*Filter)Delete(x []byte)bool
Delete deletes the item from the filter
func (f*Filter)Insert(x []byte)bool
Insert inserts the item to the filter returns error of filter is full
func (f*Filter)InsertUnique(x []byte)bool
InsertUnique inserts only unique items
func (f*Filter)LoadFactor()float64
LoadFactor returns the load factor of the filter
func (f*Filter)Lookup(x []byte)bool
Lookup says if the given item exists in filter
func (f*Filter)Encode(w io.Writer)error
Encode gob encodes the filter to passed writer
funcDecode(r io.Reader) (*Filter,error)
Decode decodes and returns the filter instance
Maximum Inserts=================Expected inserts: 16777216Total inserted: 16022242Load factor: 0.9550Time Taken: 18.118615793s=================Lookups=================Total lookups: 16022242Failed lookups: 0Expected failed lookups: 0Load factor: 0.9550Time Taken: 11.394561881s=================Maximum Inserts=================Expected inserts: 16777216Total inserted: 16525558Load factor: 0.9850Time Taken: 17.478650065s=================Lookups=================Total lookups: 16525558Failed lookups: 0Expected failed lookups: 0Load factor: 0.9850Time Taken: 12.087359139s=================Maximum Inserts=================Expected inserts: 16777216Total inserted: 16676553Load factor: 0.9940Time Taken: 16.280342789s=================Lookups=================Total lookups: 16676553Failed lookups: 0Expected failed lookups: 0Load factor: 0.9940Time Taken: 12.45013918s=================About
Cuckoo Filter: Practically better than bloom filter