# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## 1 Introduction  
In recent years, with the rapid development of positioning and mobile technology [1], a mass of applications have produced a large amount of data with different characteristics, such as spatial characteristics and temporal characteristics. Spatial characteristics are usually represented by spatial objects, such as point, line, polygon, etc. These spatial objects can be organized by one or more coordinates. In large-scale spatial analysis applications, the management of massive coordinates is an essential basic work. The management of coordinates can be regarded as the management of points. Therefore, this paper studies the management of large-scale point data. If you want to improve the efficiency of data retrieval, an appropriate index is essential. However, the indexing of high-dimensional data can be difficult because as the number of dimensions increases, the time and space costs of indexing increase dramatically. For large dimensions (20 is already enough), the indexing performance will be degraded to the most primitive sequential search, which is called 'curse of dimensionality' [2]. Nowadays, with the rapid development of big data [3] and cloud computing [4], generating massive complex high-dimensional spatial data needs a continuously updated index, as well as a quicker response, so a dynamic index is urgently needed. In the past decades, people have put forward a large number of index structures and methods to support the retrieval of data, and some of them have been widely used. Compared with other types of indexing, the easiest and most straightforward method to retrieve the data is the linear indexing which filters out the required data one by one from a data set. There is no doubt that the results can be accurately found in this way. However, the efficiency is obviously unacceptable. Another classical method is the hash table [5]. Theoretically, the time complexity it takes to find a piece of data is O(1) which is remarkable. However, the classic hash table is mainly engaged in exact matching search and it is extremely difficult to implement range queries. Another type of indexing adopts a tree structure. It performs well for its limit time complexity is usually O(lgn). In addition, it can execute range queries. The majority of spatial data indexes adopt a tree structure, such as R-tree, KD-tree, B-tree and X-tree [6]. They can be classified according to two ways, one is the way of data partition, the other is the way of space partition. Space partition trees are partitioned typically by space filling curve or the classification of each dimension of the space. The advantages of the space filling curve are that the data of any dimensions can be processed, and the data can be mapped to the one-dimensional space for coding, so that the existing B-tree [7], B\({}^{*}\)-tree [8], hash table and others can be used to perform one-dimensional space query. However, the obvious disadvantage is that at least one of them should be recoded when the indexes of different regions are combined. The index using space filling curve is extremely difficult to code in high dimensions, which makes implementation quite hard. In addition, when this method is used for range queries, there is usually a defect that some data mapping deviation is too large. There are some trees divided according to the classification of each dimension in the space, such as KD-tree [9], B-tree, etc. Firstly, they have many sub-trees in high-dimensional space. Secondly, the imbalance of the tree structure causes deeper depth of the tree, which will degrade performance and cause problems to search in a high-dimensional space. What is more, the query operation and insertion operation of these trees may be simple, while the delete operation may be more complicated because of its rebuilt sub-trees caused by the deletion of a node. There are also some variants based on KD-tree or B-tree, such as KDB-tree [10], B\({}^{+}\)tree [11], B\({}^{*}\)-tree [8], B\({}^{x}\)-tree [12].