# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Metric Indexing Techniques
\begin{table}
\begin{tabular}{l l l l} \hline \hline
**Proposition** & **Refs** & **Advantages** & **Disadvantages** \\ \hline \multirow{2}{*}{M-tree} & [241] & \(\bullet\) Balanced height structure & \(\bullet\) Problem of overlaps \\  & & \(\bullet\) Reduction of distance calculations & \(\bullet\) High cost search \\  & & & \(\bullet\) No adapted to highly grouped data \\ \hline \multirow{2}{*}{Slim-tree} & [243] & \(\bullet\) Efficient compared to M-tree \\  & & \(\bullet\) Reduced overlap rate & \(\bullet\) The overall computational complexity \\ \hline \multirow{2}{*}{Slim*+tree} & [263] & \(\bullet\) Reduces the cost of calculation during reconstructing \\  & & \(\bullet\) Avoids the unsatisfactory division & \(\bullet\) Reinserting objects is largely costly \\ \hline \multirow{2}{*}{MX-tree} & [247] & \(\bullet\) Reduces the cost of calculation during reconstructing \\  & & \(\bullet\) Avoids the unsatisfactory division & \(\bullet\) High cost search \\ \hline \multirow{2}{*}{SuperM-tree} & [250] & \(\bullet\) Capable of responding to approximate requests for subsequences or subsets & \(\bullet\) Expensive construction \\  & & \(\bullet\) Revalues only for research 1-nn \\ \hline \multirow{2}{*}{PM-tree} & [251] & \(\bullet\) More efficient similarity search compared to \\  & & \(\bullet\) Average the reconstruction compared to M-tree \\ \hline \multirow{2}{*}{DSC} & [255] & \(\bullet\) Reduces memory consumption & \(\bullet\) High amount of distance calculations \\ \cline{2-2}  & & \(\bullet\) High quality of the selected centroids \\ \cline{2-2}  & & \(\bullet\) Effective partitioning & \(\bullet\) Not support the k-nn search \\ \cline{2-2}  & & \(\bullet\) Better query performance & \(\bullet\) Lowest accuracy in small data \\ \hline Hollow-tree & [261] & \(\bullet\) Probable of managing missing data & \(\bullet\) Lowest accuracy in small data \\ \hline \hline \end{tabular}
\end{table} 
Table 16: Summary of advantage and disadvantage of metric indexing techniques based on data partitioning. \begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Proposition** & **Refs** & **Dataset Type** & **Data Dimension** & **Indexing Nature** & \multicolumn{2}{c}{**Complexity (Estimation)**} \\ \cline{3-5}  & M-tree & [241] & Synthetic data & & **Insertion and Deletion** & **Search** \\ \hline \multirow{2}{*}{Slim-tree} & [243] & Spatial, Face vectors and Test & & & \(O(mn\log_{n}(n))\) & \(O(mn\log(n))\) \\ \cline{2-5}  & & [243] & Spatial, Face vectors and Test & & & \(O(n^{2}\log(n))\) \\ \hline \multirow{2}{*}{Slim’+tree} & [263] & Image and Spatial & & & \(O(n^{2}\log(n))\) & \(O(n^{2}\log(n))\) \\ \hline \multirow{2}{*}{MX-tree} & [247] & Image, Test & & & \(O(n^{2}\log(n))+n^{2})\) & \(O(n^{2}\log(n))\) \\ \hline SuperM-tree & [250] & Synthetic data & & & not estimated \\ \cline{2-5}  & & & & & \(O(n(m+l)\log_{n}(n))\) & \(O(n^{2}log(n))\) \\ \hline DSC & [255] & Vectors, Test and Colors & & & not estimated \\ \cline{2-5}  & & & & & \(O(n\log(n))\) & \(O(kn\log(n))\) \\ \hline Hollow-tree & [261] & Synthetic & & & not estimated \\ \hline \hline \end{tabular}
\end{table} 
Table 15: Analysis of metric indexing techniques based on data partitioning.