# 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... – Mohammad Alaggan 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? – curious 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. – kodlu Jan 29 '15 at 6:16

## 2 Answers

This is not a direct answer to your question, but it's related. The probability you want is precisely what is provided by min-wise hashing schemes. In particular, a min-wise hash takes a set and produces a single element, with the property that the probability of the two elements being identical is precisely the Jaccard similarity between the sets (intersection/union).

• I've managed to create a similar scheme for (squared) cosine similarity. However I am concerned about the value of P (how many hash functions do we need), how large does it need to be to get an acceptable error rate. Do you have any references about such study for the Jaccard Similarity mentioned in the slides (or any other min-wise hashing scheme) ? Many thanks really =) – Mohammad Alaggan Jan 24 '11 at 19:00
• yes, you can get fairly precise error bounds on the number of hash functions needed. I don't know the LATEST results, but you might as well start with this paper and look at the references cited: research.microsoft.com/pubs/120078/wfc0398-liPS.pdf – Suresh Venkat Jan 25 '11 at 0:44

Maybe i am out of topic concerning the bloom filters but If you want to preserve order on encrypted data then there is a research work on that which yet is impractical. There are only theoritical constructions on that: order preserving encryption