<p>This is not a direct answer to your question,  but it's related. The probability you want is precisely what is provided by <a href="http://www.stanford.edu/class/archive/cs/cs276a/cs276a.1032/handouts/minhash-6in1.pdf">min-wise hashing schemes</a>. 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). </p>

CC BY-SA 2.5
2011-01-24T19:00:01.787Z
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
CC BY-SA 2.5
2011-01-25T00:44:45.407Z
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: http://research.microsoft.com/pubs/120078/wfc0398-liPS.pdf
Suresh Venkat
CC BY-SA 2.5
2011-01-21T16:46:36.070Z
2011-01-21T16:46:36.070Z
Suresh Venkat
<p>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: <a href="http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf" rel="nofollow">order preserving encryption</a></p>

CC BY-SA 3.0
2013-01-18T15:15:58.350Z
2013-01-18T15:15:58.350Z
curious
<p>A <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">Bloom filter</a> 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. </p>

<p>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 (<a href="http://en.wikipedia.org/wiki/Cosine_similarity" rel="nofollow noreferrer">Cosine Similarity</a> usually). However for the cryptographic version, we use the similarity between the corresponding Bloom filters of the sets instead.</p>

<blockquote>
  <p>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).</p>
</blockquote>

<p>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 <a href="https://math.stackexchange.com/questions/17241/does-this-probability-distribution-have-a-name">here</a>. I tried to search for papers studying these properties as well and I did not manage to find something of much use.</p>

CC BY-SA 2.5
2011-01-24T11:14:38.497Z
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
CC BY-SA 3.0
2013-01-18T15:11:34.270Z
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
CC BY-SA 3.0
2015-01-29T06:16:50.450Z
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
<reference-request><pr.probability>
The probability by which Bloom filters preserves the order relation given a similarity measure on sets
Mohammad Alaggan
# The probability by which Bloom filters preserves the order relation given a similarity measure on sets

(Asked by: username_0 on 2011-01-21)

A [Bloom filter](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](https://math.stackexchange.com/questions/17241/does-this-probability-distribution-have-a-name). I tried to search for papers studying these properties as well and I did not manage to find something of much use.

**Tags:** reference-request, pr.probability

> **Comments:**
> **username_0**: I wish to give the bounty on the most relavent post to correctness probability of similarity computation based on Bloom filters in particular...  
> **username_1**: 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?  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2011-01-21. Score: 6

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](http://www.stanford.edu/class/archive/cs/cs276a/cs276a.1032/handouts/minhash-6in1.pdf). 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).

> **Comments:**
> **username_0**: 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 =)  
> **username_3**: 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: http://research.microsoft.com/pubs/120078/wfc0398-liPS.pdf  

---

### Answer by username_1 on 2013-01-18. Score: 0

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](http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf)


---

