Analytic and adaptive techniques for improving nearest-neighbor search performance in k-dimensional trees

K-dimensional trees organize numeric vectors and enable efficient nearest-neighbor searches. Their geometric properties enable pruning of the search space to eliminate some unnecessary search. In this dissertation we empirically establish “best-of-breed” k-dimensional tree construction and search algorithms from the current literature. Then, we extend the amount of pruning that can be performed by increasing the amount of information stored during tree construction. Lastly, we show how clustering and feature selection techniques can be adapted and combined to enhance nearest-neighbor search efficiency based on patterns extracted from previously seen nearest-neighbor queries.