# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## Methodology
### Algorithms of HD-Tree
According to the experimental results, the algorithm performances of both trees are affected by the data distribution. However, the performance of point queries of the HD-tree is better than the D-tree in the same data. Figure 5: Projections of three differently distributed data in two dimensions. Figure 6: Experimental comparison. We measure the efficiency of range queries in terms of algorithm time and I/O quantity. As a result that the location is randomly selected and the data distribution is irregular, when a range query is performed, more time and I/Os may be spent on a smaller range. The entire range of the tested four dimensional data is defined as BV, and the range to be queried is defined as QV. Figure 6d shows the relationship between query time overhead and the size of query range. The horizontal axis represents the ratio of the range QV to be queried to the total range BV. The QV/BV ratio is from 2% to 10% in 2% step. In the experimental results, the time of the range query of the two trees increases linearly. It can be seen from the slope that both are affected by the data distribution. Under evenly distributed data (Uniform), the performance difference between the two is small. The performance of algorithm of HD-tree is significantly better than D-tree when the data are unevenly distributed (Gaussian and Cluster). The reason for this is that when the data are balanced, the number of nodes that the two trees need to find in the range query is the same (In Figure 6e, the experimental results of the data distribution as Uniform can prove this point), and the difference is mainly reflected in the speed of finding the nodes. When it is not balanced, the number of nodes to find also affects the two trees, so the gap is larger than when it is balanced. In high-dimensional space, the performance of a range query is mainly evaluated by the number of I/Os. Here, we reflect the I/O times by the number of visits to the nodes during the query. Figure 6e shows the change in the number of I/Os as a function of the QV/BV ratio. When the data are evenly distributed (Uniform), the I/O times of the HD-tree are basically equal to those of the D-tree, but the number of I/Os spent is much lower than that of the D-tree when the data are unevenly distributed (Gaussian and Cluster). Under three different data types, the number of I/Os of HD-tree is closer, which is less affected by data, but the number of I/Os in D-tree is greatly increased when the data distribution is uneven. Compared with Figure 6a, it can be found that the number of I/Os is affected by the number of nodes during range query. By summarizing the analysis of the above insert operations and query operations, we can know that HD-tree is not lower than D-tree in terms of space usage, insert performance, range query performance, etc. Generally speaking, the performance of the HD-tree is better than the D-tree, especially when the data are unevenly distributed, its performance is far better than the D-tree. In addition, the performance of HD-tree is less affected by the data than D-tree. ## 5 Conclusions

In this paper, we firstly introduced some high-dimensional indexing solutions that have been widely used and their deficiencies. Then we introduced one of the most efficient methods, D-tree, and analyzed its problems. On this basis, a high-dimensional spatial index structure, the half decomposition tree (HD-tree) is presented. The HD-tree adopts different decomposition strategies under the premise of the virtual tree structure of D-tree. Compared to D-tree, it has been greatly optimized through the half decomposition strategy (i.e., reducing the number of spatial nodes, which optimizes the space utilization; avoiding a large number of lookups to the hash table, which will greatly improve algorithm efficiency, and a small cost of disk access for range queries, with more efficient performance). Experiments prove that the space, algorithm time and disk I/O of the HD-tree are superior to those of the D-tree.