I've used Bloom filters and found them to be memory latency bound, as queries can not be cached (big data structure, random access). Any recommendations on how to speed up queries?
You could use Blocked Bloom Filters[1]. It's essentially many small Bloom Filters that each fit into a cache-line. The first hash function decides, which of the smaller Bloom Filters an element will be saved in and can still cause a cache miss. All subsequent accesses to the small Bloom Filters are cached.
The main drawback is that, because the elements won't be completely evenly distributed among the small Bloom Filters, you need some additional space to compensate and keep the false positive rate low.
1) Don't access randomly. That means either that the hash function you use is more like a reducing/mapping function (i.e. order preserving), or you iterate in the hashed order of your data. Obviously, this only works for scans and batch processes, not random user queries unless you can batch them.
2) Have a leakier bloom that fits in your L1/L2 cache size. You may have to have 2 layers of bloom filters, and this will be highly dependent on the relative expenses of the various operations.
