# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Multidimensional Indexing Techniques
#### 5.1.1. Hashing-Based Technique
Several experiments have been performed on various real-world image datasets to demonstrate its effectiveness in large-scale semantic indexing approaches. Compared to locality-sensitive hashing, the spectral hashing generates a very compact hash code, but it is not appropriate for a large and dynamic database. A new Distributed Indexing method based on Sparse-Hashing (DISH) in cloud computing was developed by [PERSON] et al. [90] to address the difficulties associated with distributing an index of high-dimensional feature vectors to multiple index nodes and search for large-scale distributed images. DISH allows documents and queries to be distributed in a balanced and redundant way between nodes. Table 3 provides a comparison of the technique discussed above. **Supervised hashing:** Supervised hashing methods are based on machine learning techniques such as decision tree [91] and neural networks [92]. These methods aim to generate intelligent indexes that can predict the unknown behavior of the data [93, 94]. The supervised hashing methods allow to treat semantic similarities as well as the search for medical images on a large scale [77, 95]. Many representative methods have used some form of supervision to design more efficient the hash functions: Kernel Based Supervised Hashing (KSH) [96], Linear Discriminant Analysis Hash (LDAHash) [97], Supervised Discrete Hashing (SDH) [98], Minimal Loss Hashing (MLH) [99], Fast Supervised Hashing (FSH) [91] and Fast Supervised Discrete Hashing (FSDH) [100]. \begin{table}
\begin{tabular}{p{56.9 pt} p{142.3 pt} p{142.3 pt} p{142.3 pt}} \hline \hline
**Proposition** & **Refs** & **Advantages** & **Disadvantages and Challenges** \\ \hline LHS & [67] & \(\bullet\) Returns with high probabilities the same bit for nearby data points in the original space by storing similar data in the same bucket & \(\bullet\) High storage cost \(\bullet\) High search time \(\bullet\) Not sufficient to processes high dimensional data. \\ \hline MultiProbe LSH & [99, 70] & \(\bullet\) Reduce the number of hash table, therefore, reduce space and time compared to LSH & \(\bullet\) Insufficient number of neighborhood candidates to respond to KNN’s requests \\ \hline Kernelized LSH & [75] & \(\bullet\) Search for approximate similarity in sub-linear time \(\bullet\) No data distribution or data entry assumptions are required & \(\bullet\) High memory consumption \(\bullet\) The search for the nearest neighbor is very difficult for high dimensional data \\ \hline BayesLSH & [71] & \(\bullet\) High quality of search results & \(\bullet\) Less effective performance \\ \hline Super-bit LSH & [73] & \(\bullet\) Significant error reduction \(\bullet\) More effective for approximate nearest neighbor recovery & \(\bullet\) Requires long hash codes and more hash tables \(\bullet\) High cost of space and time \\ \hline Asymmetric LSH & [76] & \(\bullet\) Simple and easy efficient for maximum inner product search & \(\bullet\) Does not support exact search \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of advantage and disadvantage of data independent hashing techniques. [PERSON] et al. [96] proposed a supervised hash method with kernels (KSH) in the Hamming space, where the hash codes obtained for similar data are similar hash codes (minimizes similar pairs) and for different data, the hash codes obtained are different hash codes (maximizes dissimilar pairs). [PERSON] et al. [101] proposed a discrete supervised hashing method, called Column Sampling based on Discrete Supervised Hashing (COSDISH). COSDISH operates in an iterative way, and in each iteration, several columns are first sampled from the semantic similarity matrix and then the hashing code is decomposed into two parts and alternately optimize them in a discrete way. Compared to FSH [91], which cannot use all training points due to time complexity, COSDISH is capable to use all training data points. Table 4 compares several supervised hashing techniques.