1
$\begingroup$

As I understand it, if you have a Bloom filter that was generated from the members of a specific set, you can test whether a given bit string is in the set (with some given false positive rate). The idea I had would be to run more complicated predicates on the set, like being able to query whether "there exists a member of the set which is less than target t" using a similar kind of filter. Does such a thing exist and allow you to make these queries without having to have the entire set on hand? How do they work if they exist?

$\endgroup$
1
$\begingroup$

If you want to answer arbitrary queries, no there is nothing like this. Essentially encoding a set into a Bloom filter is a process of lossy compression so that you gain efficiency in space, but the price you pay is that the data structure can answer only a specific query, i.e. set membership. Other information might have been lost because for this query it is not important.

As such, if you have a specific query in mind, you may be able to design an alternative data structure that satisfies your requirement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.