# Locality-Sensitive Hashing for Information Retrieval System on Multiple GPGPU Devices
## 4 Searching Strategy for Multiple DLSH Clusters on Multiple GPGPU Devices
### Multiple StagedLSH Hash Tables  
Due to the size of big data, the memory capacity of a single CPU/GPGPU device is not enough: distribution of the database to multiple devices is required. This problem can be tackled using a simple clustering algorithm with proper distance measurement of data/items. It is very important to deploy a clustering algorithm for real-time information retrieval systems.  
We recommend using the locality-sensitive hashing clustering algorithm to divide the data into multi-data clusters for distribution. The clustering process will be conducted before generating the hash tables. Figure 7 shows an example of clustering a data set into two sub-databases. The system creates two separate data clusters, which contain different parts of the original data set. Through the use of the LSH hash function family, we can achieve locality-sensitive data/items in the same data cluster, similar to the idea of locality-sensitive data/items in a single bucket.  
In cases in which the size of the main memory or GPGPU memory is limited, we have to limit the size of each data cluster during the clustering processing. This is a problem for many clustering algorithms, which cannot determine the limiting size for each data cluster.  
Figure 6: \(k\)NN search model with multiple GPGPUs: Master process accepting and forwarding the queries to slaves; Master process receiving and sending \(k\)NN result array to \(s\) slaves; Master process returning the \(k\)NN results array at the end.  
We propose the use of a different list of the families of hash functions to cluster the data set. In Algorithm 1, \(\hat{H_{0}}\) is the main family of hash functions for clustering, which is used to calculate the hashing index \(\hat{H_{i}}\) of \(x\). The data \(x\) will be directly assigned to a data cluster \(C_{x,0}\), if possible. Whenever the limiting size of a data cluster \(C_{x,0}\) is reached, we use the alternative hash family functions. The testing processes of these alternative \(\hat{H_{i}}\) will check other appropriate probes \(C_{x,i}\) to assign the current \(x\). This approach can also resolve the problem in which the number of devices is less than the output range of the hash function, by setting the upper bound sizes of excess data clusters to zero.  
```
0: Data set \(X\), \(\hat{H}=\{\hat{H_{0}},\hat{H_{1}},...,\hat{H_{s-1}}\}\) (\(s\) hash functions each)
0: Clustering the data set \(X\) into \(s\) data clusters \(\{X_{0},...,X_{s-1}\}\) with limited size of data clusters
1:\(\{X_{0},...,X_{s-1}\}\leftarrow\{\emptyset,...\}\)\(\triangleright\) Initialize
2:for each\(x\) in \(X\)do
3:for each family of hash function \(\hat{H_{i}}\) in \(\hat{H}\)do
4:\(hash\gets\hat{H_{i}}(x)\)\(\triangleright\)\(0\leq\)\(hash\)\(<\)\(s\)
5:if\(i\)IS_Full(\(X_{hash}\)) then
6:\(X_{hash}\gets X_{hash}\cup x\)
7: Break
8:endif
9:endfor
10:if data cluster for \(x\) was not assigned then
11:\(X_{i}\leftarrow\) Random data cluster that is not full.
12:\(X_{i}\gets X_{i}\cup x\)
13:endif
14:endfor
15:return\(\{X_{0},...,X_{s-1}\}\)
```  
**Algorithm 1** LSH clustering approach for achieving limited-size data clusters.