cuckoo-filter-ts v1.4.0
Cuckoo Filter
Typescript implementation of a Cuckoo Filter.
Introduction
A Cuckoo Filter is a probabilistic data structure that is used for set membership. It is built with the fundamentals of a Bloom Filter though offers four advantages over the Bloom Filter (as cited in the documented paper):
- Dynamic
add
anddelete
- Faster lookup time
- Easier to implement
- Uses less space (if the target false positive rate is less than 3%)
Description
A Cuckoo Filter is comprised of a n
of buckets where each bucket can store m
k
-bit sized fingprints. When inserting an object into the filter, it firsts creates a fingerprint, using MurmurHash3, then determines two buckets the fingerprint can be stored in. If either one of the buckets has space, it will be inserted into one of the two. If not, it will evict fingerprints and swap them with different buckets. This process can occur up to a configurable number of times.
Similar to a Bloom Filter, the Cuckoo Filter will determine if an object might be stored or is definitely not stored. There can be an issue with the aforementioned fourth advantage, where an existing fingerprint is inserted into the filter.
Installing
yarn
Running the tests
yarn run build
yarn run unit
License
This project is licensed under the MIT License - see the LICENSE.md file for details
Acknowledgments
- Authors of Cuckoo Filter
7 years ago