# Locality-Sensitive Hashing for Information Retrieval System on Multiple GPGPU Devices
## 4 Searching Strategy for Multiple DLSH Clusters on Multiple GPGPU Devices
### Shuffling Parallel LSH Search (S-PLSH) for Multiple DLSH Clusters  
S-PLSH is a Multi-stage search strategy that attempts to address **Problem 2**. S-PLSH can guarantee that the search probe of a query is only conducted by one slave at a time. This helps to reduce the result overflow of all queries in the buffer. By using S-PLSH, the searching order of slaves may be changed. The shuffling search method includes multiple stages and requires transferring the results from a slave to other slaves. In Figure 9, the CUStaggedLSH clusters have two devices/slaves and, so, there is a maximum of \((2+1)\) shuffle stages for the list of queries. Algorithm 2 shows the scheduling of multiple slaves in the system. First, the Master transfers the query array to all slaves. The first search stage is the most important search stage, which uses the LSH hash function to predict the buckets of all queries within it. Then, after Stage 0, two slaves need to update their results to the Master, following which the Master updates its \(k\)NN results with the new ones before sending them back to the slaves. Note that there are several queries among the slaves that cannot find their ANNs due to a missed device. Before starting the resolver stages, each slave only needs to process shuffle\(\_\)size \(=m/s\) of the unsolved queries, where \(m\) is the size of the query buffer and \(s\) is the number of slaves. Obviously, a higher number of slaves/devices leads to a higher number of search stages in S-PLSH. For a slave, a search stage of S-PLSH searches an average of \(m/s\) queries, and there is a maximum of \(s+1\) search stages (one LSH Prediction stage and \(s\) Resolver stages). However, the number of \(k\)NN results received decreases, due to sufficient content or data cluster misses; therefore, we suggest cutting out a number of final search stages, in order to increase the search speed for the trade-off of decreased \(k\)NN result quality. After conducting experiments, we suggest the use of 2-4 Resolver stages, in order to balance the speed and accuracy of S-PLSH. Another issue related to S-PLSH's scalability is the overhead of the MPI message when using a high number of slaves. If \(m\) is the number of queries and \(k\) is the number of \(k\)NN results, an ANN result uses \(2*\text{sizeof}(unit)\) bytes of storage (one unit for the index and one for the distance), and an MPI message for synchronization requires \(2 km*\text{sizeof}(unit)\) bytes as the content size. With \(s\) slaves, we have total of \(2s\) messages to be sent. However, from the second search stage, the messages  
Figure 8: Multi-stage search for an array of queries with multiple slaves. only contain \(2k/s\) results to be sent to the Master and, so, the total size required for S-PLSH is \(2 kms(2+s)*\text{sizeof}(unit)\) bytes for the whole search process. It is clear that the total content size of the packages varies linearly with the number of slaves and queries. This indicates that this topology is superior to that of broadcasting MPI messages from slaves to slaves, which requires \(s^{2}-s\) MPI messages in each synchronization step. ```
1:\(Q=\{q_{1},q_{2},...,q_{m}\}\), slave_ID, corresponding sub-database
2:RESULT (\(k\)NN result array)
3:Initialize the system: Each slave loads its data set and hash table into main memory and GPGPU memory
4:Transfer Query buffer: Master node transfers the query buffer \(Q\) to all slave; Allocate RESULT for all processes
5:State 0:\(\triangleright\) LSH Prediction stage
6:for query \(q\) in \(Q\)do
7:ifH(\(q\)) == slave_ID then
8:RESULT[\(q\)] \(\leftarrow\) CUSTagedLSHSearch(\(q\))
9:endif
10:endfor
11:Synchronize RESULT array with the Master and other slaves.