High-dimensional visual similarity search: k-d Generalized Randomized Forests

We propose a new data-structure, the generalized randomized k-d forest, or k-d GeRaF, for approximate nearest neighbor searching in high dimensions. In particular, we introduce new randomization techniques to specify a set of independently constructed trees where search is performed simultaneously, hence increasing accuracy. We omit backtracking, and we optimize distance computations. We release public domain software GeRaF and we compare it to existing implementations of state-of-the-art methods. Experimental results on SIFT and GIST visual descriptors, indicate that our method is the method of choice in dimensions around 1,000, and probably up to 10,000, and datasets of cardinality up to a few hundred thousands or even one million. For instance, we handle a real dataset of 106 GIST images represented in 960 dimensions with a query time of less than 1 sec on average and 90 responses being true nearest neighbors.