Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search
Abstract
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.
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.
Research Areas
