Ways to perform "batch" Approximate Member Queries efficiently

Question

In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number of values which I have to check if they were added to the data structure before (such that after the operation, I know which value was a member, and which weren't).

I could use a Bloom Filter and simply iterate through m, but because m is considerably large, I wanted to see if there are more efficient ways. One potentially exploitable property of the data is that most values will not be present. I'm thinking I could construct an "aggregated query" which tells me if any of the value is present or not in one operation, and do something like a binary search, but wanted to see if there is already something out there.

Some additional details:

• I can tolerate both false positives and false negatives (with predictable error rate)
• n is very large (trillions)
• m is considerably large (millions)
• Only very few values in m will be members (ca. 1 in 100K)
• The data structure can be immutable (no need for frequent writes)

Answer 1

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.)

This might be slow, however, since the lookups are random and have bad cache behavior. There are a few ways to fix this.

I'd suggest:

1. Use a blocked bloom filter (from Cache-, Hash- and Space-Efficient Bloom Filters) in which each item is mapped to a single cache-line-sized Bloom filter.

2. With the hash function that is used to map each item to a cache-line-sized Bloom filter, sort your queries in hash-value order.

3. Do the queries as usual, but in order.

Another approach is:

1. Use a split bloom filter, in which instead of setting $k$ values from a single array on each insert, set one value from each of $k$ arrays on insert.

2. After doing the inserts, use your first hash function to sort the values you wish to query in hash value order.

3. Query the first of your $k$ arrays for these values. Only a constant fraction will remain - $O(m)$ will be eliminated.

4. Take the remainder and repeat the last two steps, but using the second hash function, and the second bit array. Repeat $k$ times.

Sorting is expensive in internal memory, but it might be cheaper than all the random accesses. It depends on your machine and your data sizes.