Fast search algorithm for high dimensional pattern analysis

Nearest neighbor search is used to identify which class a query sample belongs to. The most widely used method is the shortest Euclidean distance measure and it is accepted as the simplest and most effective method for pattern analysis. In pattern analysis, we are only interested in finding out the relevant class rather than the relevant training sample, thus existing algorithms are inefficient in that they try to find an exact training sample instead of a class, so it takes a long time to decide, especially when the dimension of a dataset is very high. In this paper we will present an efficient algorithm for directly searching the nearest class instead of the nearest training sample. Experiments show that our algorithm is much more efficient than the standard tree search methodologies.