High-dimensional visual similarity search: K-d generalized randomized forests [extended abstract]

Abstract

We propose a new data-structure, the generalized random-ized k-d forest, or k-d GeRaF, for approximate nearest neigh-bor searching in high dimensions. In particular, we intro-duce new randomization techniques to specify a set of in-dependently constructed trees where search is performed simultaneously, hence increasing accuracy. We omit back-tracking, and we optimize distance computations. We re-lease public domain software GeRaF and we compare it to existing implementations of state-of-the-art methods. Ex-perimental results on SIFT and GIST visual descriptors, in-dicate that our method is the method of choice in dimen-sions 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 leb than 1 sec on average and 90% responses being true nearest neighbors. © 2016 ACM.