# Locality-Sensitive Hashing for Information Retrieval System on Multiple GPGPU Devices
## 2 Research Background and Related Works
### Locality-Sensitive Hashing (LSH)  
Note: In this section, we call the data item a point or vector, as we are examining data that include multiple values and dimensions.  
LSH uses a family of hash functions to reduce the dimensions of the data set. Then, each hash value in the new, lower-dimensional space forms a bucket containing every data point having that hash value. By using the same hash value, data points in the same bucket are closer than data points in separate buckets. The distances of buckets can also be compared by calculating the distance of hash values in the new metric space. Therefore, LSH is suitable for handling the ANN search problem in cases where the system searches in particular buckets [4; 12].  
The general LSH algorithm uses a family of hash functions to obtain the hash values. We can choose the suitable hash functions depending on the data type. Random projection functions are frequently used as the hash functions for LSH in the case of processing binary data. We denote the number of subsets or number of hash functions in the family of hash functions as \(l\), \(l\leq d\). Using \(l\) hash functions, LSH generates \(l\) subsets for every input point \(x\). This means that there are \(l\) random projection functions that transform the \(d\)-dimensional space into \(l\)-dimensional spaces. The hash table \(\mathbb{H}\) of LSH lists all of the hash values and the corresponding data points in the data set. Assuming that we are using a binary hash function, we can obtain a maximum of \(2^{l}\) different hash values, equivalent to \(2^{l}\) buckets [4; 12]. Binary hash functions are widely used in the LSH algorithm, as the resulting buckets can easily be identified [12]. We impose the number of buckets \(u\) to be equal to \(2^{l}\) in this study.  
With a hash table \(\mathbb{H}\), we can index all data points to hash values. For the ANN search problem, we must first calculate the hash value \(v\) for a query \(q\) by using the same set of hash functions \(H\) when building \(\mathbb{H}\). The hash value \(v\) indexes the set of data points \(B_{v}\) in \(B\); these data points will have the same hash value \(v\), where \(B=\{B_{i}\mid 0\leq i<2^{l}\}\) is the set of all buckets in \(\mathbb{H}\). We can use the NN result on the bucket \(B_{v}\) as the ANN result for the query \(q\):  
\[ANN_{LSH}(q)=\operatorname*{arg\,min}_{x\in B_{v}}\operatorname{Distance}(q,x). \tag{5}\]  
In practice, a threshold \(P_{1}\) is used to evaluate the accepted distance between the query and its ANN. The function \(\operatorname{CheckANN}(q,\vec{x})\) is used to evaluate the ANN candidates of the query \(q\) for all data points \(x_{i}\) in \(B_{v}\). Depending on the limited number of approximate nearest neighbors \(k\), we can stop the comparison when the number of returned neighbors reaches \(k\).  
For searching among multiple buckets, LSH needs to search within several buckets \(B_{v^{\prime}}\) that have the closest hash values to \(v\). Denote by \(P_{2}\) the threshold for evaluating the similarity between two buckets, where \(P_{2}<P_{1}\). Then, the distance between the chosen buckets \(B_{v}\) and \(B_{v^{\prime}}\) must be less than \(P_{2}\). In this case, we have more opportunities to obtain the approximate nearest neighbor for the query \(q\) from other buckets. To find \(kNN_{LSH}(q)\) for the query \(q\), LSH conducts search processes on several close buckets to find \(k\) nearest neighbors of \(q\) in these buckets. The search process for a query in a bucket is called a probe, which is the unit process of the LSH search [4; 12].