Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search

We propose two solutions for both nearest neigh- bors and range search problems. For the nearest neighbors problem, we propose a c-approximate so- lution for the restricted version of the decision prob- lem with bounded radius which is then reduced to the nearest neighbors by a known reduction. For range searching we propose a scheme that learns the parameters in a learning stage adopting them to the case of a set of points with low intrinsic dimension that are embedded in high dimensional space (common scenario for image point descrip- tors). We compare our algorithms to the best known methods for these problems, i.e. LSH, ANN and FLANN. We show analytically and experimentally that we can do better for moderate approximation factor. In contrast to tree structures, our algorithms are trivial to parallelize. In the experiments con- ducted, running on couple of million images, our algorithms show meaningful speed-ups when com- pared with the above mentioned methods.

• Machine Perception

• Information Retrieval and the Web