Try out forgetful Bloom filters

[ctb]

Via @camillescott:

http://dprg.cs.uiuc.edu/docs/fbf_cac15/fbfpaper-2.pdf

[ctb]

One interesting random (that's not directly about FBF) is to adapt this idea/cascading bloom filters to solve pre-memory allocation problem. Briefly,

• create default (small) size BF/CMS;
• when it hits a particular FP (10%?), create another larger one, position that one after the first for lookups;
• chain up to max memory usage desired;
• when FP rate of largest possible one hits a particular threshold, stop adding k-mers; either sideline reads that would have been added, OR just mix them in with the standard output stream

This could even speed things up quite a bit b/c of NUMA memory locality...

[ctb]

Or we could try cuckoo filters, http://blog.fastforwardlabs.com/post/153566952648/probabilistic-data-structure-showdown-cuckoo