kANN on the GPU with Shifted Sorting
View/
Date
2012Pay-Per-View via TIB Hannover:
Try if this item/paper is available.
Metadata
Show full item recordAbstract
We describe the implementation of a simple method for finding k approximate nearest neighbors (ANNs) on the GPU. While the performance of most ANN algorithms depends heavily on the distributions of the data and query points, our approach has a very regular data access pattern. It performs as well as state of the art methods on easy distributions with small values of k, and much more quickly on more difficult problem instances. Irrespective of the distribution and also roughly of the size of the set of input data points, we can find 50 ANNs for 1M queries at a rate of about 1200 queries/ms.
BibTeX
@inproceedings {10.2312:EGGH:HPG12:039-047,
booktitle = {Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics},
editor = {Carsten Dachsbacher and Jacob Munkberg and Jacopo Pantaleoni},
title = {{kANN on the GPU with Shifted Sorting}},
author = {Li, Shengren and Simons, Lance and Pakaravoor, Jagadeesh Bhaskar and Abbasinejad, Fatemeh and Owens, John D. and Amenta, Nina},
year = {2012},
publisher = {The Eurographics Association},
ISSN = {2079-8679},
ISBN = {978-3-905674-41-5},
DOI = {10.2312/EGGH/HPG12/039-047}
}
booktitle = {Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics},
editor = {Carsten Dachsbacher and Jacob Munkberg and Jacopo Pantaleoni},
title = {{kANN on the GPU with Shifted Sorting}},
author = {Li, Shengren and Simons, Lance and Pakaravoor, Jagadeesh Bhaskar and Abbasinejad, Fatemeh and Owens, John D. and Amenta, Nina},
year = {2012},
publisher = {The Eurographics Association},
ISSN = {2079-8679},
ISBN = {978-3-905674-41-5},
DOI = {10.2312/EGGH/HPG12/039-047}
}