# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Metric Indexing Techniques
The Onion-tree is very fast to respond the similarity search requests thanks to the increase in the number of partitions of the space compared to the MM-tree, but the problem with this structure remains in the very slow building because of the re-insertion of objects. IM-tree [223] is a proposed structure to address the problem of index degeneration posed by the fourth region of MM-tree and onion-tree. IM-tree selects the two most distant points as pivots and splits the fourth region in two using a plane. For massive data, the external region of the balls of the IM-tree becomes very large, which can then lead to the degeneration of the index. XM-tree [224] is an extension of the IM-tree [223] structure that is based on the successive division of space with spheres. XM-tree is proposed to address the problem of degeneration of the index mentioned above by focusing on minimizing the size of the outer regions of the balls. To achieve this goal, XM-tree creates extended regions inspired by the X-tree [131]. The extended regions make the Knn search very fast thanks to the elimination of some objects that are not necessary to calculate the relative distances of a query object. With the same principle of IM-tree, the NOBH-tree (Non-Overlaping Balls and Hyperplanes tree) [225] partitions the metric space through the hyper-planes and hyper-spheres to organize the data into non-overlapping regions as well as to reduce the number of distance calculations required to answer the questions. The NOBH tree recursively divides the space into several regions using the pivots (\(p_{1},p_{2}\)), and separates the data such that the distance evaluation of an element \(X_{i}\) at \(p_{1}\) and \(p_{2}\) can only contain the region \(X_{i}\). These regionsare divided using a metric hyper-plane and two spheres, where the radius of the sphere \(r\) corresponds to the distance between \(p_{1}\) and \(p_{2}\). The main drawback of this technique is the complexity of the enclosing forms. This increases the cost of insertion and search operations [224]. Ball\({}^{*}\)-tree [226] is a binary tree more balanced where each node defines a D-dimensional hyper-sphere, or a ball, that contains a subset of the points to be searched. Ball\({}^{*}\)-tree is an improvement of the original structure of Ball-tree [227; 228] proposed by [PERSON] et al. in [226]. Ball\({}^{*}\)-tree addresses the problem of data distribution and the unbalanced structure of Ball-tree by taking into account the data distribution when determining the splitting hyper-plane. In Ball\({}^{*}\)-tree the splitting hyper-plane is perpendicular to the first principal component using principal component analysis (PCA). Using this splitting technique allows to create a more balanced and efficient tree structure unlike the Ball-tree where the splitting hyper-plane is determined by the line that connects the two furthest points which creates unbalanced sub-partitions. A new indexing structure for indexing IoT data called BCCF-tree (Binary Container-based Binary Tree in Cloud-Fog Computing) was introduced by [PERSON] et al. [229]. BCCF-tree uses the k-means algorithm to partition the space into subspace without overlapping. This structure is adapted to the cloud-fog computing architecture. The aim is to improve the quality of the discovery and recovery process of large IoT data by sharing the system load among the elements of the cloud-fog computing architecture. According to the results presented in this work, the BCCF-tree shows a good performance in terms of similarity search. However, the results also show that the construction of this structure is very expensive in terms of complexity, where it reached \(O((n\cdot\log n)\cdot 2(t\cdot n))\)[230; 231]. Tables 11 and 12 present, respectively, an analytical and comparative review of metric indexing techniques based on ball partitioning.