CODEWITHSUNDEEP
bloom-filter
lapots
lapots

Reputation: 13405

using bloom filter for composite objects

As far as I understand Bloom filter allows to tell if the element does not exist in the set with 100% guarantee. But it might tell with 1% chance that element exist while in fact it doesn't.

But can it be used for complex object and keys - not just single password, id or name? For example assuming I have millions of object with distinctive characteristics (id, name, some other fields) - can I use bloom filter to check object non-existence with all those characteristics at the same time?

Upvotes: 0

Views: 266

Answers (1)

Thomas Mueller
Thomas Mueller

Reputation: 50127

Sure, you can. You have multiple choices:

  • Combine all those fields (id, name, some other field) into one combined key. And calculate the hash functions from that combined key.
  • Maintain separate Bloom filters for each field (one Bloom filter for the id, another Bloom filter for the name, one Bloom filter for the other field). When querying, you query each Bloom filter separately. The object is most likely in the set only if each of the Bloom filter returns yes. If one or more Bloom filter returns no, then the object is not definitely not in the set. This allows you to query even if you only have partial information about the object.
  • Or a combination of the two, for example one Bloom filter for the id, and one for the combination of name and other field.

Of course, having multiple Bloom filters uses more memory.

Upvotes: 1

Related Questions