A fast nearest neighbor search algorithm by nonlinear embedding
Authors:
- 1 June 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 3053-3060
Abstract
We propose an efficient algorithm to find the exact nearest neighbor based on the Euclidean distance for large-scale computer vision problems. We embed data points nonlinearly onto a low-dimensional space by simple computations and prove that the distance between two points in the embedded space is bounded by the distance in the original space. Instead of computing the distances in the high-dimensional original space to find the nearest neighbor, a lot of candidates are to be rejected based on the distances in the low-dimensional embedded space; due to this property, our algorithm is well-suited for high-dimensional and large-scale problems. We also show that our algorithm is improved further by partitioning input vectors recursively. Contrary to most of existing fast nearest neighbor search algorithms, our technique reports the exact nearest neighbor - not an approximate one - and requires a very simple preprocessing with no sophisticated data structures. We provide the theoretical analysis of our algorithm and evaluate its performance in synthetic and real data.Keywords
This publication has 14 references indexed in Scilit:
- Cover trees for nearest neighbor2006
- Real-time pattern matching using projection kernelsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2005
- iDistanceACM Transactions on Database Systems, 2005
- Independent quantization: an index compression technique for high-dimensional data spaces2002
- Finding nearest neighbors in growth-restricted metrics2002
- An optimal algorithm for approximate nearest neighbor searching fixed dimensionsJournal of the ACM, 1998
- Fast computation of the discrete Walsh and Hadamard transformsIEEE Transactions on Image Processing, 1998
- Approximate nearest neighbors1998
- R-trees1984
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975