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)
nis very large (trillions)
mis considerably large (millions)
- Only very few values in
mwill be members (ca. 1 in 100K)
- The data structure can be immutable (no need for frequent writes)