Name
Title | ||
|---|---|---|
Random Grids: Fast Approximate Nearest Neighbors and Range Searching for Image Search |
Abstract | ||
|---|---|---|
We propose two solutions for both nearest neighbors and range search problems. For the nearest neighbors problem, we propose a c-approximate solution for the restricted version of the decision problem 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 descriptors). 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. Our algorithms are trivial to parallelize. In the experiments conducted, running on couple of million images, our algorithms show meaningful speed-ups when compared with the above mentioned methods. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ICCV.2013.431 | ICCV |
Keywords | Field | DocType |
decision problem,nearest neighbors problem,random grids,range searching,common scenario,c-approximate solution,range search problem,fast approximate nearest neighbors,image search,known method,known reduction,high dimensional space,bounded radius,nearest neighbor,random processes,decision theory,learning artificial intelligence | Decision problem,Pattern recognition,Computer science,Range searching,Stochastic process,Intrinsic dimension,Decision theory,Artificial intelligence,Focus (optics),Nearest neighbor search,Bounded function | Conference |
Volume | Issue | ISSN |
2013 | 1 | 1550-5499 |
Citations | PageRank | References |
8 | 0.47 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dror Aiger | 1 | 315 | 15.76 |
| Efi Kokiopoulou | 2 | 9 | 0.82 |
| Ehud Rivlin | 3 | 608 | 40.67 |