K-Robust Nearest Neighbor Search and Classification

The nearest neighbor problem is one of the most important problems in computational geometry. Many of the solutions to this problem suffer from the "curse of dimensionality" that makes the runtime increase exponentially with the dimensionality of the point set. We explore the relaxing of the problem to the approximate nearest neighbor problem and briefly discuss its solutions before moving on to the approximate near neighbor problem. We take a detailed look at the locality sensitive hashing data structure that solves the approximate near neighbor problem. Finally, we look at a new problem: the k-robust nearest neighbor problem. We present and analyze one algorithm that solves this problem before continuing on to experiments to examine if there is any noticeable improvement in the balanced classification rate or accuracy for the k-robust nearest neighbor problem