Parallel search of k-nearest neighbors with synchronous operations


Journal Article

We present a new study of parallel algorithms for locating k-nearest neighbors (kNN) of each single query in a high dimensional (feature) space on a many-core processor or accelerator that favors synchronous operations, such as on a graphics processing unit. Exploiting the intimate relationships between two primitive operations, select and sort, we introduce a cohort of truncated sort algorithms for parallel kNN search. The truncated bitonic sort (TBiS) in particular has desirable data locality, synchronous concurrency and simple data and program structures. Its implementation on a graphics processing unit outperforms the other existing implementations for kNN search based on either sort or select operations. We provide algorithm analysis and experimental results. © 2012 IEEE.

Full Text

Duke Authors

Cited Authors

  • Sismanis, N; Pitsianis, N; Sun, X

Published Date

  • December 1, 2012

Published In

  • 2012 Ieee Conference on High Performance Extreme Computing, Hpec 2012

Digital Object Identifier (DOI)

  • 10.1109/HPEC.2012.6408667

Citation Source

  • Scopus