# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## Methodology
### Algorithms of HD-Tree
```
Input: code: Integer; Output: rec: Rectangle ifcode=1 then
1 return barcc;
2 rec, arec \(\Leftarrow\) barcc: stack \(\Leftarrow\) new Stack();
3 whilecode\(\
eq\) 1 do
4 stack.push(code & (2 dimension - 1); code \(\Leftarrow\) code \(\ll\) dimension;
5 whilestack.size()\(\
eq\) 0 do
6 index \(\Leftarrow\) stack.pop(); mark \(\Leftarrow\) 1;
7 for\(i=0\)todimension\(-1\)do
8 ifindex & mark \(\
eq\) 0 then
9 rec[i].min \(\Leftarrow\) (arec[i].min + arec[i].max) / 2;
10 rec[i].max \(\Leftarrow\) arec[i].max;
11
12 else
13 rec[i].min \(\Leftarrow\) arec[i].min;
14 rec[i].max \(\Leftarrow\) (arec[i].min + arec[i].max) / 2;
15
16 mark \(\Leftarrow\) mark \(\ll\) 1;
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
334
35
36
37
38
39
40
410
42
43
445
456
467
478
489
5900
591
592
593
594
6001
5956
5962
5979
6100
61011
61111
61111
61111
61111
61111
61111
61111
61111
61111
61111
61111
611111
61111
61111
611111
611111
611111
611111
61



point of the tree. Steps 2 and 4 show how to calculate the center of the target range. Calculating the integer code corresponding to the rectangle whose center is in the deepest part of the tree is shown from steps 5 to 11. With this encoding, we can use an integer shift operation like the D-tree until a spatial range represented by an integer encoding can contain the target (steps 12-13). ```
Input: rec: Rectangle or Point; Output: code: Integer;
1 code \(\Leftarrow\) 0; gridsize \(\Leftarrow\) 2\({}^{depth-1}\); subsize \(\Leftarrow\) \({}^{dimension}\)/2;
2 forach\(i\in[0,dimension)\)do
3 pos[i] \(\Leftarrow\) ((rec[i].max + rec[i].min) / 2 - barec[i].min) / (barec[i].max - barec[i].min) \(\times\) gridsize;
4
5 whilegridsize \(\
eq\) 0 do
6 gridsize \(\Leftarrow\) gridsize / 2;
7 for\(i=dimension-1\) to 0 do
8 if\(pos[i]\geq\)gridsizethen
9\(code\Leftarrow\)\(code+subsize\);
10\(pos[i]\Leftarrow\)\(pos[i]-gridsize\);
11\(subsize\Leftarrow\)\(subsize/2\);
12
13 while\(\
eg\) (rec \(\subseteq\) Calculate Rectangle(code)) \(\wedge\) code \(\
eq\) 1 do
14 code \(\gg\) 1;
15
16 return code;
```
**Algorithm 2**Calculate Code

#### 3.2.1 Insertion Algorithm and Deletion Algorithm

The insertion algorithm of the HD-tree is similar to the D-tree. First, the integer encoding of the target at the deepest point of the tree is calculated. Then, find the code or its prefix encodings from bottom to top in the hash table. If one of them can be found in the hash table, it means there is a node, and its corresponding rectangular range can contain the target object we want to insert. That is, we need to insert the target object into this node represented by the code we found. HD-tree can guarantee that the deepest integer encoding of the tree corresponding to the target or its upper layer encoding must have one in the hash table and there is no need to traverse the hash table. When we determine the encoding corresponding to the place to be inserted, we can insert data into the node represented by the encoding. If the number of objects in the node exceeds the maximum value, it is decomposed. Below we will introduce the decomposition algorithm of the HD-tree. Algorithm 3 shows the decomposition process of the HD-tree. The HD-tree adopts the half decomposition strategy. After spatial division, a subspace containing the most spatial objects is selected to generate a new node (steps 4-6). These spatial objects belonging to the new spatial node are added to the new node from the original node (steps 9-10). Then, calculate the depth of the new node, compare it with the original depth and choose a larger value to assign to the depth (step 11). Finally, the original node and the child node are respectively judged whether the spatial object exceeds the maximum limit, and if it exceeds, the decomposition continues, otherwise it ends (steps 12-15). The deletion of the HD-tree is also similar to the D-tree. Calculate the integer encoding of the target to be deleted in the tree, and then delete the target to be deleted from the node represented by the integer encoding or its child nodes.