# MinHash-Based Fuzzy Keyword Search of Encrypted Data across Multiple Cloud Servers
## The Proposed Fuzzy Keyword Search Scheme Based on MinHash
### A New Retrieval Method  
To further expand this scheme and make it suitable for large datasets, this paper proposes to construct a fingerprint index tree G\({}_{\text{W}}\) to improve the efficiency of search, as shown in Figure 3. When an index tree is built, the root node is generated first, which is a set that is empty. Then, the fingerprint S\({}_{i}\) of the keyword w\({}_{i}\in\) W is calculated. If S\({}_{i}\) is \(\tau\) bits in length, S\({}_{i}\) can be divided into \(\tau/\lambda\) segments with each segment being expressed using \(\alpha_{\rho}\), a binary bit stream of length \(\lambda\). S\({}_{i}\) can thus be expressed as \(\alpha_{1}\alpha_{2}\cdots\alpha_{\tau}/\lambda\) and each \(\alpha_{\rho}\) represents a node. When \(\alpha_{\rho}\) is a leaf node, (FID\({}_{\text{ij}}\), OPE(ek, Score\({}_{\text{ij}}\))) is inserted in the leaf node. Each path from the root node to the leaf node represents the fingerprint S\({}_{i}\) of a keyword. The above operation is performed for each keyword until a complete fingerprint index tree is constructed. Figure 2: Key word fingerprint generation and comparison. There are now two issues to consider. The first issue is that the simple equivalence comparison following a traditional index tree traversal method would stop as soon as the value of the compared node is different from the expected one. This obviously cannot be used for comparing Jaccard distances, neither can it be for comparing the similarity of two sets. The second issue is that if the fingerprint of a keyword and the Jaccard distance need to be calculated, traversal of the index tree needs to get to the leaf node. Therefore, if all the Jaccard distances need to be determined, traversal of the entire index tree is required, which would hardly achieve the original goal for building an index tree to improve efficiency. To achieve the goals of not necessarily traversing the whole index tree and comparing Jaccard distances, this paper proposes a new traversal method based on the characteristics of Jaccard distance as follows. Phase 1:  
Assume that the user wants to retrieve the most relevant k-documents. Before traversing the index tree, the cloud server would first construct a set U of capacity k. In the initial search phase, without any condition for decision-making, the first found leaf node can be retrieved through depth-first search and the Jaccard distance \(J_{w_{i}}\) between the root-to-leaf node path string \(S_{i}\) and the trapdoor \(T_{W}\) is calculated. The information associated with this leaf node \(\left|J_{w_{i}},\left\{\text{FID}_{b_{i}},\text{OPE}(\text{ek},\text{Score}_{i _{i}})\right\}\right|\) is then stored in U. Following the depth-first search, every leaf node will be traversed, and the associated information of each leaf node is similarly stored in U in the order of \(J_{w_{i}}\). When the set U is filled with k documents, search of leaf nodes stops although the documents in U at this point are not necessarily the final result of the search. The maximum value of \(J_{w_{i}}\) in the set U is recorded as \(J_{\text{max}}\), and execution goes into phase 2. Phase 2:  
1. When an intermediate node \(S_{i}\) is reached during the traversal, the Jaccard distance \(\hat{J}\) between the path from the root node to \(S_{i}\) and \(T_{w}\) is compared. If \(\hat{J}>J_{\text{max}}\), it implies that continuing the search from \(S_{i}\) to all the nodes beneath it will only return documents that are no more relevant than the documents in the current U. Therefore, no node after \(S_{i}\) will be traversed. Traversal of the index tree will continue only when \(\hat{J}\leq J_{\text{max}}\). 2. If a leaf node is reached in the traversal, it must be the case that \(\hat{J}\leq J_{\text{max}}\), meaning that the Jaccard distance calculated for the leaf node is less than or equal to the Jaccard distance \(J_{\text{max}}\) of U. If \(\hat{J}=J_{\text{max}}\), the content of U is not changed.