Efficient nearest neighbor search in high dimensional spaces is a problem that has numerous practical applications in the fields of statistics and machine learning, for example in robotics, computer vision, and natural language processing. In this thesis a multiple random projection trees (MRPT) algorithm for fast approximate nearest neighbor search is proposed. It is based on a variant of space partitioning trees called random projection trees (RP-trees).
Both the pseudocode of the algorithm and the actual R and C++ implementations are presented. The space and time complexity of the algorithm are analyzed. The efficiency of the algorithm is demonstrated experimentally by comparing both to the basic linear search, and to another approach of using RP-tree in approximate nearest neighbor search with moderately high-dimensional image and word frequency data sets.
Different split criteria are compared experimentally, and the optimal choice of tuning parameters of the algorithm is discussed both in theory, and demonstrated in practice with benchmark data sets.
