An Efficient k-Nearest Neighbors Approach Based on Various-Widths clustering

Abstract

The approximate k-NN search algorithms are well-known for their high concert in high dimensional data. Thelocality-sensitive hashing (LSH) method, that uses a number of hash functions, is one of the most fascinating hash-based approaches. The k-nearest neighbour approaches based Various-Widths Clustering (kNNVWC) has been widely used as a prevailing non-parametric technique in many scientific and engineering applications. However, this approach incurs a huge pre-processing and the querying cost. Hence, this issue has become an active explore field. The proposed system presents a novel k-NN based Partitioning Around Medoids (KNNPAM) clustering algorithm to powerfully find k-NNs for a query object from a given data set to minimize the extend beyond among clusters; and grouping the centers of the clusters into a tree-like index to effectively trim more clusters. Experimental results demonstrate that KNNPAM perform well in finding k-NNs for query objects compared to a number of k-NN search algorithms, mainly for a banking domain and real world data set with high dimensions, various distributions and large size. The problem of quickly finding the “exact” k-NN for a query object in a large and high dimensional data set using metric reserve functions that satisfy the triangle inequality property.KD-tree: To organization the data set in a balanced binary-tree, where the data set is recursively split into two parts along one axis .