DocumentCode :
3236968
Title :
An Improved KNN Algorithm Based on Adaptive Cluster Distance Bounding for High Dimensional Indexing
Author :
Huang Hong ; Guo Juan ; Wang Ben
Author_Institution :
Sch. of Comput. Sci. & Technol., Zhejiang Univ. of Technol., Hangzhou, China
fYear :
2012
fDate :
6-8 Nov. 2012
Firstpage :
213
Lastpage :
217
Abstract :
Because of the intense bounding and the distance of the query vector to the cluster bounding is closer to the true distance, filtering out irrelevant clusters by the distance of the query vector to the cluster bounding in the process of similarity search has well reduced the I/O complexity. Hence, the "curse of dimensionality" can be well avoided. We propose an improved KNN search algorithm based on adaptive cluster distance bounding for high dimensional indexing by reducing the CPU cost which was achieved by filtering out unnecessary distance calculations number using the triangle inequality, but with the cost of some overhead and pretreatment. Finally, we verify the improved exact KNN search algorithm has a better performance through some experiments based on a real data set.
Keywords :
indexing; information filtering; pattern clustering; query processing; search problems; I/O complexity; adaptive cluster distance bounding; curse of dimensionality; high dimensional indexing; improved exact KNN search algorithm; query vector; similarity search process; Clustering algorithms; Complexity theory; Educational institutions; Indexing; Search problems; Time factors; adaptive cluster; distance bounding; exact KNN query;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Intelligent Systems (GCIS), 2012 Third Global Congress on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4673-3072-5
Type :
conf
DOI :
10.1109/GCIS.2012.86
Filename :
6449519
Link To Document :
بازگشت