# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## Methodology
### Algorithms of HD-Tree
Finally, it is judged whether the node after deleting the data is empty. If there are no spatial objects in the node and there are no child nodes, then the node can be deleted. ```
Input: node: Leaf Node; Output:
1 code \(\Leftarrow\) node.code; max, index \(\Leftarrow\) 0;
2 rectangle \(\Leftarrow\) Calculate Rectangle(code);
3 subspace \(\Leftarrow\) Decompose Rectangle(rectangle);
4 for\(i=0\) to dimension \(-1\)do
5 ifSize(V(node, subspace[i])) \(\geq max\)then
6\(\max\Leftarrow\) Size(V(node, subspace[i])); index \(\Leftarrow\) i;
7
8 code \(\Leftarrow\) code \(\ll\) dimension + index;
9 leafnode \(\Leftarrow\) New Node(code);
10 leafnode.data.add(M(node, leafnode));
11 node.data.remove(M(node, leafnode));
12 maxdep \(\Leftarrow\) Max(maxdep, Calculate Depth(code));
13 ifSize(node.data) \(>\) maxsizethen
14 SplitNode(node);
15
16 ifSize(leafnode.data) \(>\) maxsizethen
17 SplitNode(leafnode);
```
**Algorithm 3**Split Node

#### 3.2.2 Query Algorithm and Update Algorithm

Point query can be seen as a special case of the range query, so here we only introduce the algorithm of range query. The range query of the HD-tree is shown in Algorithm 4. First, calculate the integer code in the deepest part of the tree for the rectangle to query. If the code is 0, it means the basic rectangle cannot include the target range. The query algorithm needs to be used after the target range and the basic rectangle are intersected (steps 2-3). If the code exists in the hash table, traverse the spatial objects in the node represented by the integer code, and add the spatial objects belonging to the target range to the result (steps 4-9). Then, determine in turn whether the scope represented by the subspace node and the query scope intersect. If the two have intersecting parts, add them to the queue for subsequent processing (steps 10-12). If the calculated code is not 0 and does not belong to the hash table, look up the upper node of the node corresponding to the code in turn (steps 14-19). Due to the virtual tree structure of the HD-tree, its update is very simple, as long as the target node is found for the relevant data update operation. ```
Input: rec: Rectangle; Output: result: Objects, whose position is in the rec;
1 code \(\Leftarrow\) Calculate Code(rec);
2 ifcode = 0 then
3 return Range Query(rec \(\cap\) barc);
4 ifcode \(\in\) hashthen
5 queue \(\Leftarrow\) New Queue(Get Node(code)));
6 whilequeue.peekdo
7 node \(\Leftarrow\) queue.poll();
8 ifG(node, rec)then
9 result \(\Leftarrow\) result + V(node, rec);
10 for\(i\) = 0 to \(2^{dimension}-1\)do
11 ifcode + \(i\)\(\in\) hashthen
12 queue.offer(Get Node(code + i));
13
14
15 return result;
16 whilecode \(\
eq\) 0 do
17 code \(\gg\) dimension;
18 ifcode \(\in\) hashthen
19 node \(\Leftarrow\) Get Node(code);
20 result \(\Leftarrow\) result + V(node, rec);
21 break;
22 return result;
```

**Algorithm 4**Range Query

## 4 Experimental Evaluation

In this paper, the dimensions of experimental data are 4, which are the dimensions of spatial-temporal data. We used three different sets of data to compare HD-tree with D-tree from two aspects: data insertion and query. In terms of data insertion, we mainly examine algorithm efficiency and space consumption. The queries contain point matching queries as well as range queries. For point matching queries, we only compare the expenditure of time. For range queries, we compare the algorithm time and I/O times. The computer configuration is Intel(R) Core(TM) 2.4 GHz 8 Core, 32 GB RAM. We use three simulated four-dimensional data sets for experiments. The spatial range of the three sets of data is from [0, 0, 0, 0] to [10,000, 10,000, 10,000, 10,000], and each set of data contains 100 million spatial objects. Since it is difficult to visually show the four dimensional data, we represent the distribution of the three sets of data in the form of two-dimensional projections, corresponding to the three sub-figures in Figure 5. The distribution of the first set of data is Uniform, as shown in Figure 5a.