Search code examples
data-structuresbloom-filter

Is there an open source implementation of the quotient filter?

See http://en.wikipedia.org/wiki/Quotient_filter . I did not find a single implementation yet, and I'd like something to play with, the Wikipedia explanation is a little dry for my taste.

Solution

  • I implemented a quotient filter in C (link). It supports the following operations;

    • Insert(qf, key)
    • May-Contain(qf, key)
    • Remove(qf, key) (with a caveat, see the documentation in qf.h)
    • Merge(qf1, qf2) -> qfout
    • Iterate(qf)

    The repository contains some documentation and a fairly rigorous test suite.