## 3 Preliminary Foundation
### Keyword Search Problem  
Keyword search is a typical way for users to find data stored in the cloud. Consider that there is a collection of \(n\) documents. Let \(f_{j}\) denote document \(j\) and \(K_{j}\) denote the set of  
Figure 1: The architecture of our scheme. feature words extracted from \(f_{j}\). Thus, \(K_{j}\) can be used as an abstract of the document \(f_{j}\) to characterize the document. \(K_{j}\) is comprised of certain selected keywords which have high relationship to the content of \(f_{j}\) or include all the words in \(f_{j}\), except those stop words like 'a', 'is', 'of', and 'that', etc. A dictionary is composed of all the featured words. Let \(W\) denote the dictionary, i.e., \(W=\bigcup_{j=1}^{n}K_{j}\) and assume that \(W\) is an ordered set. Further assume that there are \(m\) words in the dictionary \(W\). To facilitate the search, an index of length \(m\) is generated for each document. Specifically, let \(\mathbf{a}_{j}=[a_{1,j}a_{2,j}\dots a_{m,j}]^{T}\) denote the index vector of document \(f_{j}\), where \(a_{i,j}\) is a measurement for the relation of the word \(w_{i}\in W\) and document \(f_{j}\). A commonly used measurement for the word-document relation is based on 'Term Frequency' (TF) and 'Inverse Document Frequency' (IDF), which is defined as follows:  
\[a_{i,j}=\frac{n_{ij}}{n_{j}}\log(\frac{n}{d_{i}}), \tag{1}\]  
where \(n_{ij}\) is the number of times that \(w_{i}\) present in \(f_{j}\), \(n_{j}\) is the number of total words in document \(f_{j}\), \(d_{i}\) is the number of documents that contains \(w_{i}\), and \(n\) is the number of documents. The first term in Equation (1) is the term frequency of word \(w_{i}\) in document \(f_{j}\). If the frequency is high, it is obvious that the word has stronger relation to the document. The later term in Equation (1) represents the inverse of the fraction of documents which contains the word \(w_{i}\). It characterizes the uniqueness of a word to the corresponding documents. In general, a word, which is not present in many other documents, in a particular document is better to characterize the document. Essentially, TF-IDF characterizes the relevance of a word to a document. The higher the TF-IDF value, the stronger the relation between the word and the corresponding document. The number of documents is supposed to be large. If a user wants to search the documents, the user can provide several keywords for the topic of interest. Assume that \(R\) is the set of the keywords raised by the user. A simple search scheme is to generate a query vector \(\mathbf{q}=[q_{1}q_{2}\dots q_{m}]^{T}\) such that \(q_{i}=1\) if \(w_{i}\in W\) is one of the raised keywords in \(R\). Otherwise, \(q_{i}=0\). The query vector has the same size as the dictionary as well as the document index. To search the documents, the similarity of \(\mathbf{q}\) and \(\mathbf{a}_{j}\) for all \(j=1\dots n\) is evaluated. The similarity can be computed by the inner product of \(\mathbf{q}\) and \(\mathbf{a}_{j}\), i.e.,  
\[\mathbf{q}\cdot\mathbf{a}_{j}=\sum_{i}^{m}q_{i}\times a_{i,j},\forall 1\leq j \leq n. \tag{2}\]  
The similarity is the sum of the TF-IDF values of the words which are raised by the user and in the document index of a certain document \(f_{j}\). Since the TF-IDF indicates the relevance between the raised words and the documents, the larger the similarity, the better the corresponding documents fit the user's request. However, most of the entries in the document indexes are zero. The document index could be long, and, thus, could waste space and reduce the computation and communication efficiency. The paper wants to achieve two goals for efficient multi-keyword search based on the above system model. The first one is to increase the search efficiency. Since the number of the documents is assumed to be large, the long document index may reduce the search efficiency and occupy more space.