# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Metric Indexing Techniques
The B\({}^{+}\)-tree with MBB (Minimum Bounding Boxes) is used to index the one-dimensional data generated by the function of dimensionality reduction Space-Filling Curve (SFC) applied to the data points of the vector space. Although the structure is very \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Proposition** & **Refs** & **Advantages** & **Disadvantages** \\ \hline VP-tree & [215] & • Simple implementation & • Highest distance and time \\  & & • Research costs increase in large dimensions \\ \hline mV-tree & [216] & • Reduces research costs & • Static structure \\  & & • Little affected on a large e scale & • Support only range research & • Degradation on large scale \\ \hline MM-tree & [217] & • Best space partitioning & • Degeneration of the index (fourth region) \\  & & • Non-overlapping regions & • Regeneration of the index (fourth region) \\ \hline Onion-tree & [222] & • Better partitioning of space & • -Reinsertion- objects (semi-balancing) \\ \hline IM-tree & [223] & • Efficient compared to MM-tree and Slim-tree & • Index degeneration in massive data \\ \hline XM-tree & [224] & • Minimize the size of the search regions & • Requires high memory space \\  & & • Fast k-nn search & • Unbalanced structure \\ \hline Ball-tree & [227] & • Efficient brute force search in large dimensions & • Longer build times & • The problem of overlap not effectively addressed \\ \hline Ball\({}^{+}\)-tree & [226] & • More balanced and efficient structure compared to ball-tree & • Performance decreases as the dimensionality of the data increases \\ \hline NOBH-tree & [225] & • Non-overlapping division of the data space & • High cost of insertion and research \\ \hline BCCF-tree & [229] & • Non-overlapping division of the data space & • Erpensive construction \\  & & • Fast k-nn search & • Expensive construction \\  & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 12: Summary of advantage and disadvantage of metric indexing techniques based on ball partitioning. simple, but the construction steps such as space transformations and pre-treatment can be made parallelism is very difficult [240]. Compared between the two partitioning strategies (hyper-sphere and hyper-plane), it can be observed that the problem of node overlap is a problem that has not been effectively addressed by the techniques based on partitioning by hyper-sphere, but this problem does not exist in hyper-plane techniques (such as: GH-tree and GNAT). On the other, structures based on hyper plane partitioning are more difficult to maintain their balance because of the uncontrolled insertion positions of new elements [219]. A comparative and analytical study of metric indexing techniques based on hyper-plane partitioning is presented in Tables 13 and 14, respectively. **No Partitioning of Space (Partitioning Data):** This category does not require space partitioning. Among the families that use this type of partitioning (partitioning data), we find essentially the M-tree family. M-tree [241] is a metric free structure height-balanced allowing incremental updates based on the grouping of dynamic data into balls (or hyper-spheres). M-tree stores some data in internal or inner nodes for routing purposes and the remainder is stored in the leaf nodes. M-tree suffers from the problem of overlapping sub-spaces, which increases the number of distance calculations to answer a query [224; 242]. Several recent structures share the same principles of the M-tree and Slim-tree [243] is one of them. Slim-tree improves the structure of the M-tree with a new splitting technique based on the minimum spanning tree (MST). Slim-tree also reduces the cost of construction in addition to this, it introduces a post-processing method which reduces overlap and, consequently, the cost of research. The major disadvantage of this algorithm is the ability to generate nodes with few objects and/or empty nodes, which significantly reduces the performance of the index, especially in large spaces [244; 245; 246].