A k-Nearest Neighbor Parallel Searching Approach Using Various-Width Clustering

Ms.Aware Sneha Nandlal, Dr.Varsha H. Patil


Over recent decades, database sizes grown due to
the large used in many industrial application. Due to different
size and type of information present today, it creates the interrupt
to find the exact result of respective query. A k-nearest neighbor
searching techniques used to find the nearest result of the query
point. In this proposed system, a parallel k-nearest neighbor
approach, based on various-width clustering, to find the nearest
neighbor with parallel approach. In various-width clustering, it
creates the different size radius clusters from high, medium and
low-dimensional data sets, arrange them in set of distance and
cluster ID. The Proposed parallel k-NN search technique based
on GPU using threads, create efficient result in minimum time
space. This approach, minimizes the comparison time required
to find distance within the clusters, in addition, it also reduced
the computational cost and increase the speed up for searching

Full Text:



K. Fukunaga and P. M. Narendra, A branch and bound algorithm for

computing k-nearest neighbors, IEEE Trans. Comput., vol. C-100, no. 7,

pp. 750-753, Jul. 1975.

S. A. Nene and S. K. Nayar, A simple algorithm for nearest neighbor

search in high dimensions, IEEE Trans. Pattern Anal. Mach. Intell., vol.

, no. 9, pp. 989-1003, Sep. 1997.

R. F. Sproull, Refinements to nearest-neighbor searching in k-dimensional

trees, Algorithmica, vol. 6, no. 16, pp. 579-589, 1991.

Abdul Mohsen Almalawi, Adil Fahad, Zahir Tari, Muhammad Aamir

Cheema, and Ibrahim Khalil, kNNVWC: An Efficient k-Nearest Neighbors Approach Based on Various-Widths Clustering, IEEE Trans. Knowl.

Data Eng., vol. 28, no.1, pp. 68-81, Jan. 2016.

J. H. Friedman, F. Baskett, and L. J. Shustek, An algorithm for finding

nearest neighbors, IEEE Trans. Comput., vol. C-24, no. 10, pp. 1000-

, Oct. 1975.

A. Beygelzimer, S. Kakade, and J. Langford, Cover trees for nearest

neighbor, in Proc. 23rd Int. Conf. Mach. Learning, 2006, pp. 97-104.

P. Patella, M. Ciaccia, and P. Zezula, M-tree: An efficient access method

for similarity search in metric spaces, in Proc. 23rd Int. Conf. Very Large

Data Bases, 1997, pp. 426-435.

P. N. Yianilos, Data structures and algorithms for nearest neighbor search

in general metric spaces, in Proc. 4th Annu. ACMSIAM Sym. Discr.

Algorithms, 1993, pp. 311-321.

W. Xueyi, A fast exact k-nearest neighbors algorithm for high dimensional

search using k-means clustering and triangle inequality, in Proc. Int. Joint

Conf. Neural Netw., 2011, pp. 1293-1299.

E. Eskin, A. Arnold, M. Prerau, L. Portnoy, and S. Stolfo, A geometric

framework for unsupervised anomaly detection, in Applications of Data

Mining in Computer Security. New York, NY, USA: Springer, 2002, pp.


M. J. Prerau and E. Eskin, Unsupervised anomaly detection using an

optimized k-nearest neighbors algorithm, Undergraduate thesis, Columbia

Univ., New York, NY, USA, Dec. 2000

A. Frank and A. Asuncion. (2013). UCI machine learning repository

[Online]. Available: http://archive.ics.uci.edu/ml


  • There are currently no refbacks.


Copyright © IJETT, International Journal on Emerging Trends in Technology