PH-tree
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 -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 -dimensional keys. Like the Crit bit tree, and unlike most other spatial indexes, the PH-tree is a map rather than a multimap. A -dimensional PH-tree is a tree of nodes where each node partitions space by subdividing it into  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 -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 -dimensional key with 32bit 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  dimensions. Thus, a node can have up to  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 , to determine the quadrant where a key should be inserted (or removed or looked up), it looks at the 's bit of each dimension of the key. For a 3D node with 8 quadrants (forming a cube) the '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 's bit of the second dimension determines whether it is at the front or the back, and the 's bit of the third dimension determines bottom vs top, see picture. 1D example
Example with three 1D keys with 8bit values: ,  and . Adding  and  to an empty tree results in a single node. The two keys first differ in their 6th bit so the node has a level  (starting with 0). The node has a 5bit 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  results in one additional node at  with one quadrant containing the original node as subnode and the other quadrant containing the new key . 2D example
With 2D keys every node has  quadrants. The position of the quadrant where a key is stored is extracted from the respective bits of the keys, one bit from each dimension. The four quadrants of the node form a 2D hypercube (quadrants may be empty). The bits that are extracted from the keys form the hypercube address , for  and for . is effectively the position of the quadrant in the node's hypercube. Node structure
The ordering of the entries in a node always follows Z-ordering. Entries in a node can, for example, be stored in fixed size arrays of size . is then effectively the array index of a quadrant. This allows lookup, insert and remove with  and there is no need to store . Space complexity is however  per node, so it is less suitable for high dimensional data. Another solution is to store entries in a sorted collection, such as dynamic arrays and/or B-trees. This slows down lookup operations to  but reduces memory consumption to . The original implementation aimed for minimal memory consumption by switching between fixed and dynamic array representation depending on which uses less memory. Other implementations do not switch dynamically but use fixed arrays for , dynamic arrays for  and B-trees for high dimensional data. Operations
Lookup, insertion and removal operations all work very similar: find the correct node, then perform the operation on the node. Window queries and -nearest-neighbor searches are more complex. Lookup
The Lookup operation determines whether a key exists in the tree. It walks down the tree and checks every node whether it contains a candidate subnode or a user value that matches the key. function lookup(key) is
     entry ← get_root_entry()    // if the tree is not empty the root entry contains a root node
     while entry != NIL && entry.is_subnode() do 
         node ← entry.get_node()
         entry ← node.get_entry(key)  
     repeat
 return entry                    // entry can be NIL

 function get_entry(key) is
     node ← current node
     h ← extract_bits_at_depth(key, node.get_depth()}
     entry ← node.get_entry_at(h)  
 return entry                    // entry can be NIL

Insert
The Insert operation inserts a new key-value pair into the tree unless they key already exists. The operation traverses the tree like the Lookup function and then inserts the key into the node. There are several cases to consider:

 The quadrant is empty and we can simply insert a new entry into the quadrant and return. The quadrant contains a user entry with a key that is identical to the new entry. One way to deal with such a collision is to return a flag that indicates failed insertion. If the tree is implemented as multi-map with a collection as the node's entry, the new value is added to that collection. The quadrant contains an entry (user entry or subnode entry) with a different key. This case requires replacing the existing entry with a new subnode that holds the old and the new entry. function insert(node, key, value)
     level ← node.get_level()            // Level is 0 for root
     h ← extract_bits_at_level(key, level)
     entry ← node.get_entry(h)
     if entry == NIL then
         // Case 1.
         entry_new ← create_entry(key, value)
         node.set_entry(h, entry_new)       
     else if !entry.is_subnode() && entry.get_key() == key then
        // Case 2. Collision, there is already an entry
        return ← failed_insertion        
     else
         // Case 3.
         level_diff ← get_level_of_difference(key, entry.get_key()) 
         entry_new ← create_entry(key, value)
         // new subnode with existing entry and new entry
         subnode_new ← create_node(level_diff, entry, entry_new) 
         node.set_entry(h, subnode_new)     
     end if
 return

Remove
Removal works inversely to insertion, with the additional constraint that any subnode has to be removed if less than two entries remain. The remaining entry is moved to the parent node. Window queries
Windows queries are queries that return all keys that lie inside a rectangular axis-aligned hyperbox. They can be defined to be two -dimensional points  and  that represent the "lower left" and "upper right" corners of the query box. A trivial implementation traverses all entries in a node (starting with the root node) and if an entry matches it either adds it to the result list (if it is a user entry) or recursively traverses it (if it is a subnode). function query(node, min, max, result_list) is
     foreach entry ← node.get_entries() do
         if entry.is_subnode() then
             if entry.get_prefix() >= min and entry.get_prefix() <= max then
                 query(entry.get_subnode(), min, max, result_list)
             end if
         else
             if entry.get_key() >= min and entry.get_key() <= max then
                 result_list.add(entry)
             end if
         end if
     repeat
 return

In order to accurately estimate query time complexity the analysis needs to include the dimensionality . Traversing and comparing all  entries in a node has a time complexity of  because each comparison of -dimensional key with  takes  time. Since nodes can have up to  entries, this does not scale well with increasing dimensionality . There are various ways how this approach can be improved by making use of the hypercube address . Min  & max 
The idea is to find minimum and maximum values for the quadrant's addresses  such that the search can avoid some quadrants that do not overlap with the query box. Let  be the center of a node (this is equal to the node's prefix) and  and  be two bit strings with  bits each. Also, let subscript  with  indicate the 's bit of  and  and the 'th dimension of ,  and . Let  and . then has a `` for every dimension where the "lower" half of the node and all quadrants in it does not overlap with the query box. Similarly,  has a `` for every dimension where the "upper" half does not overlap with the query box. and  then present the lowest and highest  in a node that need to be traversed. Quadrants with  or  do not intersect with the query box. A proof is available in. With this, the above query function can be improved to:

 function query(node, min, max, result_list) is
     h_min ← calculate h_min
     h_max ← calculate h_max
     for each entry ← node.get_entries_range(h_min, h_max) do
         [ ... ]
     repeat
 return

Calculating  and  is . Depending on the distribution of the occupied quadrants in a node this approach will allow avoiding anywhere from no to almost all key comparisons. This reduces the average traversal time but the resulting complexity is still . Check quadrants for overlap with query box
Between  and  there can still be quadrants that do not overlap with the query box. Idea:  and  each have one bit for every dimensions that indicates whether the query box overlaps with the lower/upper half of a node in that dimension. This can be used to quickly check whether a quadrant  overlaps with the query box without having to compare -dimensional keys: a quadrant  overlaps with the query box if for every `` bit in  there is a corresponding `` bit in  and for every `` bit in  there is a corresponding `` bit in . On a CPU with 64bit registers it is thus possible to check for overlap of up to -dimensional keys in . function is_overlap(h, h_min, h_max) is
 return (h | h_min) & h_max == h            // evaluates to 'true' if quadrant and query overlap. function query(node, min, max, result_list) is
     h_min ← calculate h_min
     h_max ← calculate h_max
     for each entry ← node.get_entries_range(h_min, h_max) do
         h ← entry.get_h();
         if (h | h_min) & h_max == h then   // evaluates to 'true' if quadrant and query overlap. [ ... ]
         end if
     repeat
 return

The resulting time complexity is  compared to the  of the full iteration. Traverse quadrants that overlap with query box
For higher dimensions with larger nodes it is also possible to avoid iterating through all  and instead directly calculate the next higher  that overlaps with the query box. The first step puts ``-bits into a given  for all quadrants that have no overlap with the query box. The second step increments the adapted  and the added ``-bits trigger an overflow so that the non-overlapping quadrants are skipped. The last step removes all the undesirable bits used for triggering the overflow. The logic is described in detail in. The calculation works as follows:

 function increment_h(h_input, h_min, h_max) is
     h_out = h_input | (~ h_max )        // pre - mask
     h_out += 1                          // increment
     h_out = ( h_out & h_max ) | h_min   // post - mask
 return h_out

Again, for  this can be done on most CPUs in . The resulting time complexity for traversing a node is . This works best if most of the quadrants that overlap with the query box are occupied with an entry. -nearest neighbors
 nearest neighbor searches can be implemented using standard algorithms. Floating point keys
The PH-tree can only store integer values. Floating point values can trivially be stored as integers casting it them an integer. However, the authors of also propose an approach without loss of precision. Lossless conversion
Lossless converting of a floating point value into an integer value (and back) without loss if precision can be achieved by simply interpreting the 32 or 64 bits of the floating point value as an integer (with 32 or 64 bits). Due to the way that IEEE 754 encodes floating point values, the resulting integer values have the same ordering as the original floating point values, at least for positive values. Ordering for negative values can be achieved by inverting the non-sign bits. Example implementations in Java:
long encode(double value) {
    long r = Double.doubleToRawLongBits(value);
    return (r >= 0) ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}

Example implementations in C++:
std::int64_t encode(double value) {
    std::int64_t r;
    memcpy(&r, &value, sizeof(r));
    return r >= 0 ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}

Encoding (and the inverse decoding) is lossless for all floating point values. The ordering works well in practice, including  and . However, the integer representation also turns  into a normal comparable value (smaller than infinity), infinities are comparable to each other and  is larger than . That means that, for example, a query range  will not match a value of . In order to match  the query range needs to be . Hyperbox keys
In order to store volumes (axis-aligned hyper-boxes) as keys, implementations typically use corner representation which converts the two -dimensional minimum and maximum corners of a box into a single key with  dimensions, for example by interleaving them: . This works trivially for lookup, insert and remove operations. Window queries need to be converted from -dimensional vectors to -dimensional vectors. For example, for a window query that matches all boxes that are completely inside the query box, the query keys are:

For a window query operation that matches all boxes that intersect with a query box, the query keys are:

Scalability
In high dimensions with less than  entries, a PH-tree may have only a single node, effectively “degenerating” into a B-Tree with Z-order curve. The add/remove/lookup operations remain  and window queries can use the quadrant filters. However, this cannot avoid the curse of dimensionality, for high dimensional data with  or  a PH-tree is only marginally better than a full scan. Uses
Research has reported fast add/remove/exact-match operations with large and fast changing datasets.. Window queries have been shown to work well especially for small windows or large dataset

The PH-tree is mainly suited for in-memory use. The size of the nodes (number of entries) is fixed while persistent storage tends to benefit from indexes with configurable node size to align node size with page size on disk. This is easier with other spatial indexes, such as R-Trees. Implementations
 Java: GitHub repository by original inventor
 C++: GitHub repository by original inventor
 C++: GitHub repository
 C++: GitHub repository

See also
 Binary space partitioning
 Binary tiling
 k-d tree
 Octree
 Quadtree
 R-tree
 UB-tree
 Spatial database

External links

 PH-tree website with detailed description, examples and performance comparison

References 

Trees (data structures)
Database index techniques
Geometric data structures