A Recursive Partitioning Method for Nearest Neighbor Search in High Dimensional Data

摘要

Many real world applications require searching a large amount of data to find the objects similar to the search queries. Nearest Neighbour Search is the common operation that has been used to conduct similarity search in vast areas like Content-Based Image Retrieval, Web search engines, micro array data analysis etc. Dimensionality forces us to look at data from a different perspective when dealing with such large data. In this work we propose a recursive partitioning and distance-based indexing scheme for large and high-dimensional data to retrieve the nearest neighbours for a given query. This method works by dividing the data space into disjoint partitions based on the distance from a reference point to the data objects. In the next level for each sub-partition a reference point is selected and again it is partitioned into further sub-sub-partitions. Main advantage of this method is that it reduces the search space. To find the nearest neighbours we use Soergel distance metric which is a dissimilarity-based distance metric to find the association between two data objects. We are able to retrieve the top 100 nearest neighbours (kNN) by searching in only a single bin where all the nearest neighbours lie for the given query according to the distance from a reference point. We have validated our method by conducting experiments with the following data sets: ZINC data set, AT and T Faces Database. Our results show that the proposed method is having a very less construction (off-line) time and search (on-line) time compared to brute-force linear scan. Proposed method reduces or prunes the search space from 100 percent to 10 percent or even less, which will save lot of computation time. We verified the proposed method with other methods and compared the performance and the results are presented.