K-d trees are multi-dimensional (e.g., k-dimensional) search trees used for a large number of different applications in computer science. K-d trees are a special case of binary space partitioning trees and can be used for searches involving a multidimensional search key, such as range searches and nearest neighbor searches. Every non-leaf node of a k-d tree can be thought of as implicitly generating a splitting hyperplane that divides the space into two half-spaces. Points to the left of the splitting hyperplane are represented by the left sub-tree of that node. Points to the right of the hyperplane are represented by the right sub-tree. One key advantage of k-d trees is that in their “left-balanced and complete” form their entire topology can be encoded by simply arranging the points in the proper order, without requiring any memory for storing the tree topology.
A number of serial and parallel algorithms exist for building k-d trees, with proven optimal O(N log N) run time complexity. However, all algorithms known in the art require a temporary copy of the data to be stored in memory, which can be prohibitive for large data sets, which may include billions of data points. Existing techniques work by recursively finding the m-th median out of a list of points, while using a properly chosen m to ensure a balanced tree. The techniques then use that element as a sub-tree's root node, and recurse the list of points to the left and right of that point, respectively. These techniques require constant re-arranging of the as-yet-unprocessed particles, so existing techniques typically use two lists of particles: one list for the points that are not yet placed and one list for the final array of where nodes are written into as soon as their position is determined.
USPTO Backgrounds
USPTO Backgrounds