# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Metric Indexing Techniques  
Formally, a metric space \((\mathcal{O},d)\) is a set of points \(\mathcal{O}\) (where, \(\mathcal{O}\
eq\varnothing\)) to which we associate a notion of distance \(d(\mathcal{O}\times\mathcal{O})\rightarrow\mathbb{R}^{+}\) between the elements that meets the following properties:  
* _Non-negativity_ : \(\forall(x,y)\in\mathcal{O}^{2},d(x,y)\geq 0\);
* _Identity_ : \(\forall x\in\mathcal{O},d(x,x)=0\);
* _Symmetry_ : \(\forall(x,y)\in\mathcal{O}^{2},d(x,y)=d(y,x)\);
* _Triangle inequality_ : \(\forall(x,y,z)\in\mathcal{O}^{3},d(x,y)+d(y,z)\leq d(x,z)\). **Partitioning of Space:** In the literature, two partitioning techniques have been developed: the first technique is based on hyper-sphere (or ball) partitioning as in: VP-tree [215], mVP-tree [216] and MM-tree [217], etc. while the second technique is based on hyper-plane partitioning as in: GH-tree [218], GNAT-tree [55] and EGNAT-tree [219], etc. **Hyper-sphere (or Ball) partitioning**: VP-tree [215] is a hierarchical indexing structure such as Kd-tree, developed to improve the search for similarity in a metric space. VP-tree is a technique based on the partitioning of the space through the balls according to distance. VP-tree uses the median distance between the vantage point (choose randomly) and the points of the space to partition the space in two balanced disjoint sub-spaces. The disadvantage of the VP-tree is the highest cost in terms of calculated distance as well as time, especially as the data space has a large dimension where the number of branches searched for is high [220]. The mV-tree is proposed to address the problem of reduced performance in the search for similarity of the VP tree in high-dimensional metric spaces. mV-tree (multiple Vantage Points tree) [216] is an extension of the VP-tree idea that uses several vantage points instead of one. The major advantage of mV-tree over VP-tree is that it also uses pre-computed distances (at the construction step) to improve search speed and reduce the number of distance calculations as well as the time required to execute queries. The experiments presented in [215] show that mV-tree improves the VP-tree slightly better but not in all cases, while a greater improvement is achieved when several pivots per node are used [61]. [PERSON] et al. [221] proposed the DMVP-tree structure to accelerate the recovery process of similarity images in the airport's video surveillance system. This approach is an improvement of the metric indexing structure MVP-Tree [216] using the horizontal distribution of MVP-Tree structure in several machines to overcome massive high-dimensional spatial indexing problems. The DMVP-tree structure partitions the space horizontally where the upper area is called \"main space\" and the lower areas are called \"secondary spaces\". The main space is indexed in MVP-Tree that stored in the master machine and the secondary space is partitioned in a static way on the slave machines. MM-tree [217] is another indexing structure for metric space that also uses the principle of recursive partitioning of space through balls in two non-overlapping regions. MM-tree is an unbalanced structure due to the different size of sub-spaces (or regions), due to the external region of the balls. To solve this problem, MM-tree applies an additional a semi-balanced algorithm that allows to re-organize the objects of the leaf nodes. According to the experiences presented by [222], MM-tree does not support high-dimensional data. Several structures have been proposed based on the MM-tree structure. All these structures are developed to address the challenges of the MM-tree structure (Onion-tree [222], IM-tree [223] and XM-tree, the extended Metric tree [224]). Onion-tree [222] is an MM-tree improvement proposed to overcome the challenges or limitations of the MM-tree structure.