Haar Wavelet Transform Based Fast K-Nearest Neighbor Search Algorithm

摘要

The task of k-nearest neighbor search is to find the k nearest neighbors of a query vector in the data set. Due to the orthogonality of the Haar wavelet transform, the k nearest neighbors, searching in the spatial domain, are the same as that in the wavelet domain. In addition, the transform can compress the energy into a few wavelet coefficients with low computational complexity. Therefore, some fast KNN algorithms based on Haar wavelet are proposed. This paper is to provide a review of those algorithms.