Talk:Quotient filter

Nominated: Did you know ...

Link to reference implementation

I'd like to add a link to this reference implementation of the quotient filter to the article. Since I'm the author it would be best if someone else makes the decision to include or omit the link :-).

I think the link should be added because my implementation is relatively complete and well-tested. There is also a precedent for linking to reference implementations (see AVL_tree).

OTOH, my implementation is not notable. There may also be technical defects in it (despite my best efforts).

-vk (talk) 08:03, 3 September 2014 (UTC)

Disputing credit for the structure

Despite publication of the Quotient Filter papers, the basic Quotient filter was not in any way invented by the authors. First, there is no structural change from the 1984 Cleary paper, except that (IIRC) Cleary leaves implicit the need for 'occupied' bits. The only conceptual change is using the structure to store hash fingerprints, for a probabilistic filter structure. Though I would argue this is not a significant enough conceptual change for primary credit, even in that case, the 2005 paper An Optimal Bloom Filter Replacement (link goes to 2011 journal version) does this in Section 5. And then the 2009 paper Fast, All-Purpose State Storage uses it in the same way and even describes an optimization for getting the three metadata bits down to two, in Section 2.3.

Thus, the publication of this "Don't thrash: how to cache your hash on flash" paper was a regression in reported state-of-the-art, at least with respect to the basic structure they call a Quotient Filter. Although "quotient filter" might now be the accepted name, and they can be credited with the name and raising awareness of the structure, the world had already been introduced to all the ideas of basic Quotient Filters before this paper. — Preceding unsigned comment added by Pfunk42 (talk • contribs) 00:30, 10 November 2018 (UTC)