Abstract:
The nearest neighbour problem is of practical significance in a number of fields such as bioinformatics, multimedia libraries, information retrieval etc. Finding an object near to a given query object is often a matter of interest. The problem is old, and a large number of solutions have been proposed in the literature. Many of these solutions need to build a model before answering the query. Most of the time the dataset is large or dynamic, we either opt for the strategy which does not need to build the model or move to some other solutions like approximations. The solution which uses some model may give answers efficiently but the drawback is model-building process, which is time consuming. These methods may answer the queries in less time but the model building process suppresses this advantage.
We have made an attempt to speed up the model building process using multicore architecture in order to reduce the pre-processing time. We have chosen cover tree data structure for model-building on multicore architectures because it scales well for large and high dimensional dataset.
In this dissertation entitled, "AN EFFICIENT IMPLEMENTATION OF NEAREST NEIGHBOUR MODELS ON MULTICORE GPU ", a parallel algorithm for cover tree model building is proposed which implements a model of cover tree on Compute Unified Device Architecture (CUDA) in order to fasten the model-building process. In order to implement this parallel algorithm, an iterative cover tree algorithm is also proposed. A variant of cover tree data structure is also proposed for better parallelization. The proposed strategy can be extended to other algorithms which need model building.
We have implemented the proposed iterative cover tree algorithm for model-building using single core CPU and proposed cover tree algorithm for parallel architecture. We have also implemented our proposed variant of cover tree for single and multicore architectures. The results obtained from run time statistics of proposed algorithm show significant gain in speedup over linear algorithm.
