Closest Point Search in High Dimensions
Abstract
The problem of finding the closest point in high-dimensional spaces is common in computational vision. Unfortunately, the complexity of most existing search algorithms, such as k-d tree and R-tree, grows exponentially with dimension, making them impractical for dimensionality above 15. In nearly all applications, the closest point is of interest only if it lies within a user specified distance /spl epsiv/. We present a simple and practical algorithm to efficiently search for the nearest neighbor within Euclidean distance /spl epsiv/. Our algorithm uses a projection search technique along with a novel data structure to dramatically improve performance in high dimensions. A complexity analysis is presented which can help determine /spl epsiv/ in structured problems. Benchmarks clearly show the superiority of the proposed algorithm for high dimensional search problems frequently encountered in machine vision, such as real-time object recognition.
Cite
Text
Nene and Nayar. "Closest Point Search in High Dimensions." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1996. doi:10.1109/CVPR.1996.517172Markdown
[Nene and Nayar. "Closest Point Search in High Dimensions." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1996.](https://mlanthology.org/cvpr/1996/nene1996cvpr-closest/) doi:10.1109/CVPR.1996.517172BibTeX
@inproceedings{nene1996cvpr-closest,
title = {{Closest Point Search in High Dimensions}},
author = {Nene, Sameer A. and Nayar, Shree K.},
booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
year = {1996},
pages = {859-865},
doi = {10.1109/CVPR.1996.517172},
url = {https://mlanthology.org/cvpr/1996/nene1996cvpr-closest/}
}