# HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy
## Methodology
### Algorithms of HD-Tree  
The HD-tree is an improvement on the D-tree, so some algorithms similar to the D-tree are not described here or simply described. Suppose the number of dimensions of the basic rectangle is dimension, the basic rectangle is barec, the maximum number of spatial objects that each node can contain is maxsize, the hash table containing codes is hash and the maximum depth of the tree is maxdep. Our HD-tree consists of a series of nodes. As shown in Figure 4a, a node contains two fields, where the code is the integer encoding of the node, and data are the set of spatial objects contained in the node. The objects in data have a value in each dimension. We use position to represent the set corresponding to these values, namely {a\({}_{0}\), a\({}_{1}\)... a\({}_{dimension-1}\)}. Each node has a corresponding spatial range, and each range query also requires a range. Here we use a rectangle to represent a range. Figure 4b shows the structure of a rectangle. The rectangle has a minimum and a maximum in each dimension. After introducing some basic data structures, we need to introduce some related functions. The first is \(V(N,R)\). Given a node \(N\) and a rectangle \(R\), find a set of objects, which are spatial objects in \(N\), and they are included in the range of \(R\), defined as Equation (1). \[V(N,R)=\{p|p\in N.data,p.position\subseteq R\}. \tag{1}\]  
Given a rectangle \(R\) and another rectangle \(AR\). When they meet the conditions in Equation (2), the minimum value of \(R\) in each dimension is not greater than the maximum value of \(AR\) in the corresponding dimension, and the maximum value of \(R\) in each dimension is not less than the maximum value of \(AR\) in the corresponding dimension. If the condition is met, indicating that the two rectangles intersect, we return true, otherwise return false. We use \(G(R,AR)\) to indicate this judgment condition. \[ \begin{split}\forall i\in&\{0,1,..dimension-1\},\\ & R[i].min\leq AR[i].max\wedge R[i].max\geq AR[i].min.\end{split}  \tag{2}\]  
Figure 4: (a) Structure of spatial node, (b) structure of rectangle. Given a node \(N\) and another node \(LN\), we need to find a set of objects, so that these objects are both objects in \(N\), and these objects are included in the range represented by the code corresponding to the node. We write this function as \(M(N,LN)\), defined as Equation (3). \[ \begin{split} M(N,LN)=\{p|p\in N.data,\\ p.position\subseteq Calculate\ Rectagalle(LN.code)\}.\end{split}  \tag{3}\]  
Now we begin to formally introduce algorithms. The first algorithm to be introduced is to find the corresponding rectangle in the tree according to the integer code. As shown in Algorithm 1, all values after the highest bit of an encoding are added to the stack in order from low to high (steps 4-5). If a code of a four-dimensional HD-tree is 0 \(\times\) 123, then 3, 2 are sequentially placed on the stack. The value here represents which sub-rectangle we need after a rectangle decomposition. We pop the values in the stack in order, decompose the rectangle and get the corresponding sub-rectangle until the stack is empty, returning the last sub-rectangle (steps 6-17). How to get the range of the sub-rectangle is shown from step 7 to step 10.