Research On K-nearest Neighbor Search Algorithm In High Dimensional Space

In computer vision,machine learning,multimedia data mining and many other fields,k nearest neighbor search is common and essential.Because its efficiency could affect that of the entire algorithm in a large extent,a more efficient k nearest neighbor search algorithm could benefit many applications substantially.At present,there are many efficient search algorithms in low dimensional space,but their efficiency decreases greatly when they process high dimensional data.In order to cope with the plight of dimensional curse,many algorithms propose an approximate search scheme.Although these algorithms can meet the needs of most applications,some applications need the algorithm to return the exact k nearest neighbor search results.As discussed above,this paper propose a more efficient and exact k nearest neighbor search algorithm for high dimensional space.In this paper,the algorithm has mainly two stages: data pre-processing and k nearest neighbor search.In the pre-processing stage,we focus vector distance information in a few dimensions through orthogonal transformation and dimensionality reduction,which makes the algorithm only need to handle a small number of dimensions in the query phase to complete the majority of work and thus effectively reduces search time effectively in the high dimensional space.In the search phase,this paper first design an approximate nearest neighbor search algorithm,which can quickly get high quality nearest neighbor search results when it runs independently.As for accurate k nearest neighbor search,we use it to return a threshold.Next,the algorithm filters the data that is not likely to become a k nearest neighbor through continuously loading the partial dimensions of the data and using the threshold returned by the approximate nearest neighbor search algorithm.At last,the algorithm could complete exact k nearest neighbor search only by loading a small amount of data from the disk.Experiments show that this algorithm can effectively filter the data through a small portion of the dimension and return the exact k nearest neighbor search results more efficiently.