The PH-tree is a tree data structure used for spatial indexing of multi-dimensional data (keys) such as geographical coordinates, points, feature vectors, rectangles or bounding boxes. The PH-tree is space partitioning index with a structure similar to that of a quadtree or octree. However, unlike quadtrees, it uses a splitting policy based on tries and similar to Crit bit trees that is based on the bit-representation of the keys. The bit-based splitting policy, when combined with the use of different internal representations for nodes, provides scalability with high-dimensional data. The bit-representation splitting policy also imposes a maximum depth, thus avoiding degenerated trees and the need for rebalancing.
Overview The basic PH-tree is a spatial index that maps keys, which are d-dimensional vectors with integers, to user defined values. The PH-tree is a multi-dimensional generalization of a Crit bit tree in the sense that a Crit bit tree is equivalent to a PH-tree with 1 {\displaystyle 1} -dimensional keys. Like the Crit bit tree, and unlike most other spatial indexes, the PH-tree is a map rather than a multimap. A d-dimensional PH-tree is a tree of nodes where each node partitions space by subdividing it into 2 d {\displaystyle 2^{d}} quadrants (see below for how potentially large nodes scales with high dimensional data). Each quadrant contains at most one entry, either a key-value pair (leaf quadrant) or a key-subnode pair. For a key-subnode pair, the key represents the center of the subnode. The key is also the common prefix (bit-representation) of all keys in the subnode and its child subnodes. Each node has at least two entries, otherwise it is merged with the parent node. Some other structural properties of PH-trees are:
They are 2 n {\displaystyle 2^{n}} -ary trees. They are inherently unbalanced but imbalance is limited due to their depth being limited to the bit width of the keys, e.g. to 32 for a d {\displaystyle d} -dimensional key with 32-bit integers. Insertion or removal operations cause exactly one node to be modified and potentially a second node to be added or removed. This can be useful for concurrent implementations. This also means little variation in modification cost. Their structure is independent from insertion/removal order.
Splitting strategy Similar to most quadtrees, the PH-tree is a hierarchy of nodes where every node splits the space in all d dimensions. Thus, a node can have up to 2 d {\displaystyle 2^{d}} subnodes, one for each quadrant.
Quadrant numbering The PH-tree uses the bits of the multi-dimensional keys to determine their position in the tree. All keys that have the same leading bits are stored in the same branch of the tree. For example, in a node at level L, to determine the quadrant where a key should be inserted (or removed or looked up), it looks at the L's bit of each dimension of the key. For a 3D node with 8 quadrants (forming a cube) the L's bit of the first dimension of the key determines whether the target quadrant is on the left or the right of the cube, the L's bit of the second dimension determines whether it is at the front or the back, and the L's bit of the third dimension determines bottom vs top, see picture.
1D example Example with three 1D keys with 8-bit values: k 0 = { 1 } b a s e 10 = { 00000001 } b a s e 2 {\displaystyle k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}} , k 1 = { 4 } 10 = { 00000100 } 2 {\displaystyle k_{1}=\{4\}_{10}=\{00000100\}_{2}} and k 2 = { 35 } 10 = { 00100011 } 2 {\displaystyle k_{2}=\{35\}_{10}=\{00100011\}_{2}} . Adding k 0 {\displaystyle k_{0}} and k 1 {\displaystyle k_{1}} to an empty tree results in a single node. The two keys first differ in their 6th bit so the node has a level L = 5 {\displaystyle L=5} (starting with 0). The node has a 5-bit prefix representing the common 5 bits of both keys. The node has two quadrants, each key is stored in one quadrant. Adding a third key k 3 {\displaystyle k_{3}} results in one additional node at L = 2 {\displaystyle L=2} with one quadrant containing the original node as subnode and the other quadrant containing the new key k 2 {\displaystyle k_{2}} .
… excerpt ends here. Continue reading the full article.
