Is there an open source implementation of the quotient filter?

Question

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.

Answer 1

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.

Answer 2

I implemented one in PHP for the purpose of playing around with it. It's not complete but add/contains is implemented. This is not fool proof or even bug proof.

https://github.com/dsx724/php-quotient-filter

Hope this helps.