Nearest Neighbour (NN) search is an essential and important problem in many areas, including multimedia databases, data mining and computer vision. For low-dimensional spaces a variety of tree-based NN search algorithms efficiently cope with finding the NN, for high-dimensional spaces, however, these methods are in-efficient. Even for Locality Sensitive Hashing (LSH) methods which solve the task approximately by grouping sample points that are nearby in the search space into buckets, it is difficult to find the right parameters. In this paper, we propose a novel hashing method that ensures a high probability of NNs being located in the same hash buckets and a balanced distribution of data across all the buckets. The proposed method is based on computing a selected number of pairwise uncorrelated and uniformly-distributed Circular Random Variables (CRVs) from the sample points. The method has been tested on a large dataset of SIFT features and was compared to LSH and the Fast Library for Approximated NN search (FLANN) matcher with linear search as the base line. The experimental results show that our method significantly reduces the search query time while preserving the search quality, in particular for dynamic databases and small databases whose size does not exceed 200k points.
展开▼
