# The probability by which Bloom filters preserves the order relation given a similarity measure on sets

A Bloom filter is a data structure for probabilistic set-membership. When adding an item to the set, $k$ bits (whose indices are determined by $k$ different hash functions) are set to 1. To check if an item is a member of the set, those $k$ bits are checked to be equal to 1. Deletions are no supported and there is a probability of false positives.

Bloom filters are usually used make digests of big sets. In our case they are used to represent a set of items a certain user are interested in. Our clustering algorithm uses the similarity between the sets of two users (Cosine Similarity usually). However for the cryptographic version, we use the similarity between the corresponding Bloom filters of the sets instead.

What I am seeking as whether there is any references regarding the conditional probability that the similarity between two Bloom filters will tell us something about the similarity between the corresponding sets, and to which degree Bloom filters preserve the order relation on Cosine Similarity (or other similarity measures).

I have been doing some work on that, and it gets pretty deep, lots of combinatorics and multi-set coefficients. I've posted a related question here. I tried to search for papers studying these properties as well and I did not manage to find something of much use.

• I wish to give the bounty on the most relavent post to correctness probability of similarity computation based on Bloom filters in particular... Jan 24 '11 at 11:14
• What do you mean for the cryptographic verion? you encrypt data, then you extract some features on them (you use a fixed size chunk based extraction) you add them in a bloom filter and then you suppose that 2 similar unencrypted data will look similar after apply on them the same similarity detection algorithm used at the unencrypted version which in that case is sth like lookups in a BF? Jan 18 '13 at 15:11
• Or do you use a cryptographic hash function to decide which bits are to be turned on. They are not easy to analyse for your purposes. Jan 29 '15 at 6:16