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