PH-tree

<p>The PH-tree is a <a href="/facts/Tree_data_structure/RcXz9noF">tree data structure</a> used for <a href="/facts/Spatial_index/wzPAetLd">spatial indexing</a> of multi-dimensional data (keys) such as geographical coordinates, points, <a href="/facts/Feature_vector/nzAhYxfu">feature vectors</a>, rectangles or <a href="/facts/Bounding_box/oFHL8bxI">bounding boxes</a>.  
The PH-tree is space partitioning index with a structure similar to that of a <a href="/facts/Quadtree/6b23FQoD">quadtree</a> or <a href="/facts/Octree/hNT74wvT">octree</a>. However, unlike quadtrees, it uses a splitting policy based on <a href="/facts/Trie/cXNr0ScT">tries</a> and similar to <a href="/facts/Crit_bit_tree/a1JKJPYc">Crit bit trees</a> 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 <a href="/facts/Binary_tree/TDV7GMpu">degenerated trees</a> and the need for rebalancing.
</p>

PH-tree open-in-new

PH-tree