High-dimensional approximate nearest neighbor: k -d Generalized Randomized Forests

Yannis Avrithis (1) , Ioannis Z. Emiris (2) , Giorgos Samaras (3)

1 LinkMedia - Creating and exploiting explicit links between multimedia fragments
2 ERGA - Laboratory of Algebraic and Geometric Algorithms [Kapodistrian Univ]
3 NKUA - National and Kapodistrian University of Athens

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 ran-domization 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 , thus accelerating queries. We release public domain software GeRaF and we compare it to existing implementations of state-of-the-art methods including BBD-trees, Locality Sensitive Hashing, randomized k-d forests, and product quantization. Experimental results indicate that our method would be the method of choice in dimensions around 1,000, and probably up to 10,000, and pointsets of cardinality up to a few hundred thousands or even one million; this range of inputs is encountered in many critical applications today. For instance, we handle a real dataset of 10 6 images represented in 960 dimensions with a query time of less than 1sec on average and 90% responses being true nearest neighbors.

Mots clés: data-structure; randomized tree; space partition; geometric search; open software; practical complexity

Domaines: Algorithme et structure de données [cs.DS]

Yannis Avrithis, Ioannis Z. Emiris, Giorgos Samaras. High-dimensional approximate nearest neighbor: k -d Generalized Randomized Forests. 2016. ⟨hal-02370318⟩