Ways to perform "batch" Approximate Member Queries efficiently
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:


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.
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.
Do the queries as usual, but in order.


Another approach is:


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.
After doing the inserts, use your first hash function to sort the values you wish to query in hash value order.
Query the first of your $k$ arrays for these values. Only a constant fraction will remain - $O(m)$ will be eliminated.
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.