Title :
Haar Wavelet Transform Based Fast K-Nearest Neighbor Search Algorithm
Author :
Qiao, Yu-Long ; Guo, Tao
Author_Institution :
Coll. of Inf. & Commun. Eng., Harbin Eng. Univ., Harbin, China
Abstract :
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.
Keywords :
Haar transforms; query processing; search problems; vectors; wavelet transforms; Haar wavelet transform orthogonality; computational complexity; energy compression; fast k-nearest neighbor search; query vector; spatial domain; Approximation algorithms; Approximation methods; Classification algorithms; Nearest neighbor searches; Signal processing algorithms; Wavelet transforms; Haar wavelet transform; k-nearest neighbor search;
Conference_Titel :
Pervasive Computing Signal Processing and Applications (PCSPA), 2010 First International Conference on
Conference_Location :
Harbin
Print_ISBN :
978-1-4244-8043-2
Electronic_ISBN :
978-0-7695-4180-8
DOI :
10.1109/PCSPA.2010.221
