# Locality-Sensitive Hashing for Information Retrieval System on Multiple GPGPU Devices
## 2 Research Background and Related Works
### k-Nearest Neighbors (kNN) Search Problem  
In conventional information retrieval systems, the most crucial problem is finding similar data/items for the input query. Items are considered similar if the distance between them is small, in terms of the associated metric space [8]. Thus, to examine the similarity of two items, we observe the distance between them. There are three common problems related to the similarity searching problem: \begin{table}
\begin{tabular}{r l l} \hline \hline  & \(x,q\) & \(\triangleq\) & Item, query item \\  & \(d\) & \(\triangleq\) & Number of dimensions of data \\  & \(X=\{x_{1},x_{2},...,x_{n}\}\) & \(\triangleq\) & Data set with \(n\) items \\  & \(s\) & \(\triangleq\) & Number of data clusters/slaves \\ \(\hat{X}=\{X_{0},X_{1},...,X_{s-1}\}\) & \(\triangleq\) & Sub-data sets \\ \(H=\{h_{1},h_{2},...,h_{1}\}\) & \(\triangleq\) & Set of \(l\) hash functions \\  & \(\mathbb{H}/\mathbb{H}_{i}\) & \(\triangleq\) & Hash table/Sub-hash tables \\ \(B=\{B_{0},B_{1},...,B_{u-1}\}\) & \(\triangleq\) & Set of \(u\) buckets in the hash table \\ \(\vec{x_{j}}\) & \(\triangleq\) & Pointer/index to item \(x_{j}\) in \(X\) \\ \(\hat{H}=\{\hat{H}_{0},\hat{H}_{1},...,\hat{H}_{s-1}\}\) & \(\triangleq\) & Families of hash functions for clustering \\  & \(k\) & \(\triangleq\) & Number of \(k\)NN results for each query \\ \(Q=\{q_{1},q_{2},...,q_{m}\}\) & \(\triangleq\) & Set of \(m\) query items \\  & \(K\) & \(\triangleq\) & Array of \(k\)NN results of \(Q\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: List of abbreviations. Nearest Neighbor Search (NNS) problem: The problem of finding the point \(x^{*}\in X\) that is closest to the query point \(q\), using:  
\[x^{*}=NN(q)=\operatorname*{arg\,min}_{x\in X}\operatorname{Distance}(q,x), \tag{1}\]  
where \(\operatorname{Distance}(,)\) is the distance function in the \(d\)-dimensional space \(\mathbb{R}^{d}\) and \(\operatorname*{arg\,min}\ ()\) is the argument of the minimum function, which returns the optimal argument. To find the most similar item to the query, it is necessary to compare the query to all items in the data set [9]. The most similar item can be identified as the nearest neighbor (NN) of the query [8]. However, finding the exact NN is extremely difficult when dealing with a big data set [10]. Approximate Nearest Neighbor (ANN) search problem: the ANN search is a modification of the NNS, which estimates the nearest neighbor using a threshold [10]. Find a point \(x\in X\) for the given query point \(q\), in such a way that  
\[ANN(q)=x\mid\operatorname{Distance}(q,x)\leq c*\operatorname{Distance}(q,x^{* }), \tag{2}\]  
where \(x^{*}\) is the nearest neighbor of \(q\) in \(X\) and \(c\) is the approximation factor. Using the ANN Search, we can reduce the complexity of the search algorithm by sharply decreasing the number of comparisons between the query point \(q\) and points in \(X\)[11]. In practice, the distance from the query to its true nearest neighbor is estimated by using a training data set [10]. \(P_{1}\) denotes the estimated threshold for determining the ANN; \(P_{1}\) may be different depending on the requirements of different systems. Equation (2) becomes:  
\[ANN(q)=x\mid\operatorname{Distance}(q,x)\leq P_{1}. \tag{3}\]  
\(k\)-Nearest Neighbors (\(k\)NN) search problem: Using multiple ANN results can increase the convenience of the information retrieval system for real-world cases. We choose \(k\) ANN points \(x\) for the query \(q\):  
\[kNN(q)=\{x|\operatorname{Distance}(q,x)\leq P_{1},\ x\in X\}\quad\text{with} \quad|kNN(q)|=k. \tag{4}\]  
In this study, if the number of accepted items is less than \(k\), we still use \(k\) memory locations to store \(kNN(q)\) by setting the empty locations to a NIL value. The item order in \(kNN(q)\) should be sorted by increasing similarity with the query \(q\). Most information retrieval systems using the \(k\)NN search provide multiple choices for the user. We consider the \(k\)NN search problem as the main problem to solve.