# 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 l l l} \hline \hline
**Proposition** & **Refs** & **Dataset Type** & **Data Dimension** & **Indexing Nature** & \multicolumn{2}{c}{**Complexity (Estimation)**} \\ \cline{2-6} \cline{6-6} \cline{7-7} \cline{10-10} _BS-tree_ & [232] & Point data & & & \(\mathsf{O}(\pi\log_{n}(\pi))\) & \(\mathsf{not}\) estimated \\ \hline _GH-tree_ & [218] & Not mentioned & & & & \(\mathsf{O}(\pi\log_{n}(\pi))\) & \(\mathsf{O}(n\log(\pi))\) \\ \hline _GNAT-tree_ & [55] & Image, text, Vectors & & & & \(\mathsf{O}(\pi\log_{n}(n))\) & \(\mathsf{O}(\frac{n}{\pi}\log(n))\) \\ \hline _EGNAT-tree_ & [219] & Words and coordinate space & Multidimensional & & & \(\mathsf{O}(\pi\log_{n}(\pi))\) & \(\mathsf{O}(\frac{n}{\pi}\log(n))\) \\ \hline _GHB-tree_ & [236] & Geographic coordinates and image & & & \(\mathsf{O}(\pi\log(n))\) & \(\mathsf{O}(2k\log_{n}(k))\) \\ \hline _CD-tree_ & [237] & Image & & & \(\mathsf{O}(\pi\log(n))\) & \(\mathsf{O}(n\log(n))\) \\ \hline _SPB-tree_ & [238; 239] & Words, Colors, DNA, Signature and Synthetic & & & & \(\mathsf{O}(\pi lx+n\pi\log_{n}(n))\) & not estimated \\ \hline \hline \end{tabular}
\end{table} 
Table 13: Analysis of metric indexing techniques based on hyper-plane partitioning. \begin{table}
\begin{tabular}{l l The work of [PERSON] et al. [247] aims to avoid unsatisfactory node partitioning and reduce regional overlap in the M-tree structure [241; 248]. The authors proposed a new metric indexing structure called M\({}^{X}\)-tree based on the original M-tree structure. M\({}^{X}\)-tree implements the concept of super-nodes inspired by the [131] structure of the X-tree. This structure avoids the unsatisfactory division of nodes, thus reducing the cost of computation and extends it completely to metric space where temporal complexity is reduced to \(O(n^{2})\) without setting any parameter. As for the M tree, the temporal complexity reaches \(O(n^{3})\). The authors also add another strategy to the M\({}^{X}\)-tree structure to improve the management of free memory space that is represented in the indexing of tree leaf objects in an internal index [249] through the vantage-point tree (VP-tree) [215]. Due to the symmetry of the metric axioms of metric space, metric indexing techniques such as M-tree and their variances cannot answer to the approximate requests of sub-sequences or subsets. [PERSON] [250] propose an improvement on the M-tree structure called SuperM-tree to create a metric indexing structure capable of responding to the approximate requests of sub-sequences or subsets such as searching for a similar partial sequence of a gene, a similar scene in a film, or a similar object in an image. The author introduces a new metric measurement subset space \"Metric Subset Space (M; d; v)\" to create this structure. It ignores the symmetry of metric axioms and adds a new relationship on object size (for more details on the demonstration of this new space, see article [250]). The efficiency of the search in M-tree is reduced when the volume is high, thus, Pivoting M-tree (PM-tree) is proposed [251; 252] to resolve this problem. PM-tree is a hybrid structure, which combines the \"local-pivoting strategies\" of M-tree [241] with the \"global-pivoting strategies\" of LAESA [253]. Recently, [PERSON] et al. [254] presented a new construction algorithm for the two indexing structures M-tree and PM-tree. The objective is to enhance the performance of Knn requests. The construction algorithm is based on storing data once in the tree (M-tree or PM-tree) through the deletion of promoted elements that are stored in the upper level of the leaf nodes during their partitioning. To achieve this idea, the authors use the aggregate nearest query to find the most efficient local pivots that will be promoted during the partitioning of internal nodes.