cuckoo-filter: Pure and impure Cuckoo Filter

[ data, library, mit, program ] [ Propose Tags ]


Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS],,,,
Change log
Dependencies aeson, base (>=4.7 && <5), cereal, containers, criterion, cuckoo-filter, hashable, random [details]
License MIT
Copyright 2018 Chris Coffey
Author Chris Coffey
Category Data
Home page
Bug tracker
Source repo head: git clone
Uploaded by ChrisCoffey at 2018-10-30T01:59:16Z
Distributions NixOS:
Executables benchmarks
Downloads 2678 total (9 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-11-02 [all 1 reports]

Readme for cuckoo-filter-

[back to package description]


HackageBuild Status

Cuckoo filters are a probabilistic data structure used to answer questions like "Have I already seen this user" or "Is this word in the English language?". They're probabilistic because each membership operation has a false positive probability. It guarnatees that there will never be a false negative, but may have a low chance of false positives.

Bloom filters are the cannonical probabilistic filter structure, and cuckoo filters are a simlar but different tool. As a bloom filter's load factor increases, the chance of false positive trends towards 100%, but the inserts will never fail. On the other hand, a Cuckoo filter retains a relatively stable false positive probability under load, but as load approahes 95% inserts will begin to fail. In either case you probably want to resize your filter...

This implementation has the following properties:

  • Buckets of 4 elements
  • 8 bit fingerprints
  • Cycle termination during item kicking occurs after (0.1 * size) buckets have been checked.
  • Size may be any non-zero natural number (not limited to powers of 2)

For more details about how Cuckoo filters work, I recommend you read Fan et. al.'s 2016 paper


Cuckoo filters support three operations: insert, member, and delete. See the haddocks for details.


As you'll find in the criterion results, the pure version of the filter can handle ~1.6 million insertions/s. From memory profiles, the vast majority of the memory is taken up by the underlying implementation of Filter, so this is an obvious area for improvement.

The current implementation avoids pre-allocating memory for the filter, so the heap usage will incrase linearly with insert calls. This obviously helps keep heap usage low for sparse filters, but also means inserts are slower than they would be in a mutable implementation.


  • Benchmark against a Bloom filter implementation
  • Introduce a mutable version of Filter and a typeclass for the storage interactions