kANN on the GPU with Shifted Sorting

Eurographics DL Repository

Show simple item record

dc.contributor.author Li, Shengren en_US
dc.contributor.author Simons, Lance en_US
dc.contributor.author Pakaravoor, Jagadeesh Bhaskar en_US
dc.contributor.author Abbasinejad, Fatemeh en_US
dc.contributor.author Owens, John D. en_US
dc.contributor.author Amenta, Nina en_US
dc.contributor.editor Carsten Dachsbacher and Jacob Munkberg and Jacopo Pantaleoni en_US
dc.date.accessioned 2013-10-28T10:23:56Z
dc.date.available 2013-10-28T10:23:56Z
dc.date.issued 2012 en_US
dc.identifier.isbn 978-3-905674-41-5 en_US
dc.identifier.issn 2079-8679 en_US
dc.identifier.uri http://dx.doi.org/10.2312/EGGH/HPG12/039-047 en_US
dc.description.abstract 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. en_US
dc.publisher The Eurographics Association en_US
dc.subject Categories and Subject Descriptors (according to ACM CCS): I.3.1 [Computer Graphics]: Hardware Architecture- Parallel processing I.3.1 [Computer Graphics]: Hardware Architecture-Graphics processors F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-Sorting and searching en_US
dc.title kANN on the GPU with Shifted Sorting en_US
dc.description.seriesinformation Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics en_US

Files in this item

Pay-Per-View via TIB Hannover:

Try if this item/paper is available.

This item appears in the following Collection(s)

Show simple item record

Search Eurographics DL


My Account