# 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}{p{42.7 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
**Proposition** & **Refs** & **Dataset Type** & **Data Dimension** & **Indexing Nature** & \multicolumn{2}{c}{**Complexity (Estimation)**} \\ \cline{4-6}  & & & & **Insertion and Deletion** & **Search** \\ \hline VP-tree & [215] & Images & Dynamic & & \(O(n\log_{n}(n))\) & \(O(n^{2}\log(n))\) \\ \hline mV-tree & [216] & Images & Static & & \(O(n\log_{n}(u))\) & \(O(nm\log(n))\) \\ \hline MM-tree & [217] & Image and Geographic coordinates & & & \(O(n^{2}\log_{n}(n))\) & \(O(n^{2}\log(n))\) \\ \hline Onion-tree & [222] & Image, Time-series and Geographic coordinates & & Multidimensional & \(O(n^{2}\log(n))\) & \(O(n^{2}\log(n))\) \\ \hline IM-tree & [223] & Image & & & \(O(n\log(n))\) & \(O(c_{mn}\log(n))\) \\ \hline XM-tree & [224] & Geographic and Image & & & \(O(nmx\log(n))\) & \(O(c_{mn}\log(n))\) \\ \hline Ball-tree & [227; 228] & Not mentioned & & & \(O(n\log(n))\) \\ \hline Ball\({}^{*}\)-tree & [226] & Synthetic and Point data & & & \(O(\frac{n}{2}\log(n))\) \\ \hline NOBH-tree & [225] & Image and Synthetic & & & \\ BCCF-tree & [229] & Synthetic, Geographic coordinates and wearable action recognition database & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Analysis of metric indexing techniques based on ball partitioning. **Hyper-plane partitioning**: The first indexing structures that are based on the partition of space through hyper-planes are the oldest structure BS-tree (Bisector tree) [232] and the structure GH-tree (Generalized Hyper-plane tree) [218] which is similar to BS-tree. GH-tree is a binary indexing structure that divides the space recursively into two sub-spaces through the hyper-plane which is defined by the two representative points or pivots (the two farthest points as in [233; 234; 235]) the rest of the points are partitioned according to the distance between these pivots. The drawbacks of this structure reside in the search process where at each node two distance operations are performed which increases the cost of the search, as well as the selected pivots does not guarantee the best partition of space, which makes the problem of index degeneration possible. GNAT-tree (Geometric Near-neighbor Access Tree) [55] is a static indexing structure. GNAT-tree is a generalization of the GH-tree which uses \(m\) pivots in each internal node instead of two (i.e., GNAT-tree is an \(m\)-ary tree). Regarding EGNAT-tree [219], it is the dynamic structure of GNAT-tree. Recently, GHB-tree (Generalised Hyper-plane Bucketed) [236] is proposed as an improvement of the GH-tree structure. The objective of the GHB-tree structure is created a balanced indexing structure with less construction cost through the new type of node that they called a bucket. These types of nodes found at the leaf level which has a limited capacity to store a subset of the most similar data to improve the search process. The CD-Tree, cited in [237], is a type of index based on hyper-plane partitioning. This indexing approach has proven effective for a limited number of dimensions but remains ineffective for large dimensions. The recursive partitioning of space into two regions is the principle of this technique. Two pivots are chosen each time, and each one is associated with the closest objects. However, the problem with this technique is that the geometrical shapes of the regions pose many problems in the search algorithm. A new metric indexing structure called SPB (Space filling curve and Pivot based B\({}^{+}\)-tree) tree was proposed by [PERSON] et al. [238; 239]. The method was proposed to improve the efficiency of similarity search, support large number of complex objects and reduce the cost in terms of storage, construction and search (i.e., reduces CPU and I/O cost). To achieve these objectives, SPB-tree uses geometric information not available in metric space through the mapping of objects in a metric space to data points in a vector space using well-chosen pivots.