# A Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues
## 5 Existing Indexing Techniques
### Multidimensional Indexing Techniques
#### 5.1.2 Tree-Based Technique
Due to this type of node, X-tree supports the indexing of large data with less overlap and less performance reduction compared to the R-tree structure. X-tree is a hybrid index that consists of a hierarchical part (tree) and a linear part (list). X-tree is a variable structure where size and complexity is difficult to calculate because of their sensitivity to size, distribution of data [141]. In addition, X-tree consumes a lot of memory space for storage and its performance is limited with the data dimension. R-tree nodes and its variants reduce the number of partitions that occur in the construction of the R-tree and increase the spatial utilization of the R-tree to solve the problem of overlapping, which influences the construction performance and requests efficiency. [PERSON] et al. [142] proposed a new lazy splitting strategy to optimize the R-tree generation process. Bloom Filter Matrix (BFM) is a multidimensional data indexing structure developed by [PERSON] et al. [143] to solve the problem of decreasing index performance for high-dimension data. BFM uses a multidimensional matrix based on the Cartesian product of bloom filters where each filter represents an attribute of the original data. Although the BFM structure demonstrates a multi-attribute data indexing speed and search accuracy, it suffers from a very high space consumption [144], which makes it inadequate for IoT applications where data is massive. For an efficient R-tree index, [PERSON] et al. [145] proposed a new retrieval method, called the Dynamic Clustering Center (DCC) method, which allows choosing the optimal cluster center according to the distance indicator R during the construction of the R-tree spatial index. This technique aims to make R-tree structure more compact, reduce multipath searches and improve search efficiency. The requirement to classify data flow records such as web traffic flow monitoring, spam detection and intrusion detection is addressed in [146]. A new E-tree indexing structure with a time complexity less than \(O(log_{n})\) was proposed by [PERSON] et al. to organize all base classifiers in an ensemble for fast prediction. E-tree used a balanced height structure like an R-tree to reduce the expected prediction time from linear complexity to sublinear complexity. On the other hand, E-tree is automatically updated by the repeated aggregation of new classifiers and the elimination of those that are relevant or obsolete. It therefore adapts well to discover new trends and patterns and undifferentiated data flows [146; 147]. E-tree requires a high storage space and maintenance [148] despite the results of the analysis showing the effectiveness of this approach. ER\({}^{+}\)-tree is a new multidimensional data indexing. The structure on the cloud-computing infrastructure was proposed by [PERSON] in [149]. This structure is a hybrid tree structure that combines the benefits of E-tree [146] and R\({}^{+}\)-tree [137]. The main objective of this structure is to reduce computation time and improve the quality of the similarity search in a cloud-computing environment [149]. The idea of combining these two structures is to create a more efficient structure in terms of balancing and similarity research. The E-tree structure is used to partition the data flow to reduce overload, while the R\({}^{+}\)-tree structure is used to reduce search time and improve the quality of the similarity search through its Minimum Boundary Rectangle (MBR). In [150], [PERSON] and [PERSON] introduced a tree indexing structure based on R\({}^{*}\)Q-tree. This approach improves query performance and reduces indexing costs. It is based on the \(k\)-means clustering algorithm to reorganize nodes between neighboring nodes in the tree. In addition, a new indexing method (SUSHI) was proposed by [PERSON] et al. [151]. This method is based on subspace clustering for indexing high dimensional objects, where the construction of the index tree is done in a recursive way. The nodes of each level represent the groups resulting from the subspace clustering method.