High-dimensional visual similarity search: K-d generalized randomized forests [extended abstract]
AuthorAvrithis, Yannis S.
Emiris, Ioannis Z.
Samaras, George S.
PublisherAssociation for Computing Machinery
SourceACM International Conference Proceeding Series
33rd Computer Graphics International Conference, CGI 2016
Google Scholar check
MetadataShow full item record
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.