NEAREST NEIGHBOR SEARCH WITH RANDOM PROJECTION TREES

摘要

The invention concerns a hyperplane-partitioned spatial indexing tree, such as a random projection tree that indexes data having a high dimensional ambient space. The invention also concerns estimating at least one nearest neighbor data point of a given query point using the tree. In particular the invention searches a hyperplane-partitioned spatial indexing tree for at least one nearest neighbor of a given query point. The tree indexes data having a high dimensional ambient space and low intrinsic dimensionality. The method recursively searches through nodes of the tree, and at each node searched updates as appropriate the current nearest neighbor identified. Also, at each node, a shortest distance (QB) on the intrinsic space between the query point and a splitting hyperplane bounding that node is determined. If this shortest distance is greater than a predetermined value (QG), disregarding in this search any node that is also bounded by that splitting hyperplane. Aspects of the invention include a method, computer system and software.