# MinHash-Based Fuzzy Keyword Search of Encrypted Data across Multiple Cloud Servers
## The Proposed Fuzzy Keyword Search Scheme Based on MinHash
### Preliminaries
#### 3.1.1 Jaccard Similarity  
Jaccard similarity, also known as Jaccard coefficient, is a measure of similarity based on the metrics of distance [22]. The definition of Jaccard coefficient is as follows:  
**Definition 1** (Jaccard coefficient): _Given two finite sets \(A\) and \(B\), the Jaccard coefficients of \(A\) and \(B\) J(\(A\), \(B\)) is defined by the following equation:_  
\[\mathrm{J(A,B)=|\,A\cap B|\,/\,|\,A\cup B|} \tag{1}\]  
As can be seen in Equation (1), the Jaccard similarity of sets A and B is equal to the number of common elements of the two sets divided by the total number of elements in them. It is clear that Jaccard similarity falls into the range [0, 1].  
Definition 2 (Jaccard coefficient): _Jaccard similarity (A, B) can convert to Jaccard distance using the following equation:_  
\[\text{Jaccard Distance (A, B) = 1 - J(A, B)} \tag{2}\]  
It is thus clear from Equation (2) that the bigger the Jaccard similarity, the more similar the two objects that are involved and the smaller the distance between the two objects.  
To derive the similarity of object sets, we can use a feature matrix in which each column represents a set and each row expresses the same element of all the object sets. If an element appears in the corresponding row of a set, then the value of the row is set to 1, otherwise, it is set to 0. For example, for the set S = {a, b, c, d, e} in which the four object sets are S\({}_{1}\) = {a, d}, S\({}_{2}\) = {c}, S\({}_{3}\) = {b, d, e} and S\({}_{4}\) = {a, c, d}, the matrix of the four object sets is shown in Table 1.  
Using Equation (1), the Jaccard similarity of sets S\({}_{1}\) and S\({}_{4}\) is 2/3 in the above example.  
Definition 3 (MinHash Signature): _Given a random sequence \(A\) of \(n\) elements, the MinHash signature \(h_{min}\)(A) of the sequence is defined as follows:_  
\[\text{h}_{\text{min}}(\text{A})=\underbrace{\text{min}}_{\text{j}\in\text{A}} \pi(\text{j}) \tag{3}\]  
Definition 4 (MinHash Function): _Given two finite sets \(A\) and \(B\), the probability that the two sets have the same value of MinHash is defined as:_  
\[\text{Pr}\{\text{h}_{\text{min}}(\text{A})=\text{h}_{\text{min}}(\text{B})\}= \text{J}(\text{A},\text{B}) \tag{4}\]  
In applications, the MinHash function generates multiple hash for the target items so that similar items are more likely to hash into the same bucket than dissimilar ones. Moreover, if a document with at least one element being hashed into the bucket is considered to be a candidate, similarity between candidates can be examined to find similar documents in the candidate set.  
For two sets A and B, \(\text{h}_{\text{min}}(\text{A})=\text{h}_{\text{min}}(\text{B})\) means that any element with its MinHash value in A\(\cup\)B is also in A\(\cap\)B. The hypothesis is that h(x) is a good Hash function if it has good homogeneity since it can map different elements to different integers. Therefore, the similarity of sets A and B is the same as the probability that the MinHash values of A and B are the same after passing through the Hash. Furthermore, the probability that they become the candidate pair is \(1-\left(1-\text{S}^{\text{L}}\right)^{\text{K}}\), where S is the Jaccard similarity of sets A and B.