7
$\begingroup$

In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter.

This idea is presented in Zhong et al., Optimizing data popularity conscious bloom filters, PODC '08 and Bruck et al., Weighted Bloom filter, IEEE Information theory '06. However, I know of an independent and roughly contemporary "discovery" of this idea in industry that wasn't published.

This idea seems like the kind of thing that may have been independently discovered multiple times and I'd like to find the earliest public reference to cite. It's possible this exists somewhere in the IR literature as a variant of "signature files", or elsewhere with terminology that I'm not familiar with.

In the IR literature, there's Faloutsos et al., Design of a signature file method that accounts for non-uniform occurrence and query frequencies, VLDB '85, which is quite close but if I'm reading the paper correctly the paper only does the math for splitting terms into two separate classes and doesn't generalize the math like Zhong et al. or Bruck et al.

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't know much about this area, so the following may not be related, but M. Mitzenmacher did some work explaining the "power of two choices" in randomized load balancing, in his 1996 PhD thesis. And searching for ["power of two choices" Bloom] throws up this 2007 paper by Lumetta and MM. The references in those papers may point somewhere. FWIW, MM wrote a survey of Bloom filters and I see references in Zhong et al to his papers, so vaguely related at least. $\endgroup$
    – ShreevatsaR
    Commented Dec 27, 2016 at 18:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.