# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## Methodology
### Algorithms of HD-Tree
In Figure 5b, the distribution of the second set of data is a Gaussian distribution from the origin; that is, it spreads outward from the origin, and the more outside, the less data. The distribution of the third group of data is shown in Figure 5c. We randomly select 100 positions in the space as the center of each cluster, and distribute 1 million data near each center. Similarly, the further away from the center of the cluster, the less data. The three sub-figures in the subsequent experimental results correspond to the three sets of data mentioned above. Why not choose some existing benchmark data sets? Since the D-tree is a form of spatial division and adopts a full decomposition strategy, it can be guessed that the D-tree is greatly affected by the data distribution. In addition, through experiments, it can also be proved that the data distribution has a great influence on the D-tree. Therefore, we generated three data sets with different distributions which have more obvious characteristics than some existing benchmark data sets and can better reflect the impact of differently distributed data on D-tree and HD-tree. ### Insertion Performance Evaluation

To evaluate the space usage of HD-tree and D-tree, we set the maximum number of spatial objects allowed in a node to be 128. We continuously insert 100 million spatial objects, reflecting the space utilization of the two trees by the number of nodes, because we use a node to map a disk page. Figure 5(a) reflects the number of nodes used to insert 100 million spatial objects. When the data distribution is evenly distributed, as the data are continuously inserted, a large number of nodes are quickly decomposed due to the complete decomposition strategy. Then, in the process of inserting data for a long time, there is no decomposition or only a few nodes are decomposed, because the data are evenly distributed, the previously decomposed nodes can also accommodate a large amount of data. Nodes of HD-tree are continuously decomposed with the inserted data; thus, the HD-tree does not occupy many nodes like the D-tree when the data volume is small. It can be seen that no matter what kind of data distribution, the consumption of space of the HD-tree is not higher than the D-tree, especially when the data are unevenly distributed, nearly half of the space can be saved. Although the distribution of the data had an impact on the number of nodes, the HD-tree had a slight impact. Figure 5(b) shows the time taken to insert objects. Regardless of the data distribution, under the same data, the time consumption of the HD-tree is much less than that of the D-tree. In the first two types of data (Uniform and Gaussian), the HD-tree uses only half the time of the D-tree, and the last data (Cluster) consume less than 20% of the time of the D-tree. The main reason is that in the case of uneven data distribution, the probability that the D-tree cannot find the deepest integer code or the upper layer codes is greatly increased. It needs a lot of sequential lookups to the hash table, so the time is greatly increased. In addition, the performance of the insertion of the three data sets of the HD-tree is closer, which means it is less affected by the data distribution. ### Query Performance Evaluation

In this paper, we will compare the query performance of HD-tree and D-tree by point query and range query, respectively. Since disk performance is greatly affected by other factors, we do not compare disk time, but rather the performance of algorithm and the number of I/Os. Figure 5(c) reflects the time spent on point queries (100 million spatial objects). The two trees are both virtual tree structures, a single point query only needs one disk I/O, so the I/O of the point query of them is the same, without any significance of comparison. The algorithm performance gap between them can be mainly reflected in three places (i.e., calculate the integer code of the data in the deepest part of the tree, look up the code or its upper codes in turn in the hash table, and traverse the data in the node).