Skip to main content

Parallel search of k-nearest neighbors with synchronous operations

Publication ,  Journal Article
Sismanis, N; Pitsianis, N; Sun, X
Published in: 2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012
December 1, 2012

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.

Duke Scholars

Published In

2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012

DOI

Publication Date

December 1, 2012
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Sismanis, N., Pitsianis, N., & Sun, X. (2012). Parallel search of k-nearest neighbors with synchronous operations. 2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012. https://doi.org/10.1109/HPEC.2012.6408667
Sismanis, N., N. Pitsianis, and X. Sun. “Parallel search of k-nearest neighbors with synchronous operations.” 2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012, December 1, 2012. https://doi.org/10.1109/HPEC.2012.6408667.
Sismanis N, Pitsianis N, Sun X. Parallel search of k-nearest neighbors with synchronous operations. 2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012. 2012 Dec 1;
Sismanis, N., et al. “Parallel search of k-nearest neighbors with synchronous operations.” 2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012, Dec. 2012. Scopus, doi:10.1109/HPEC.2012.6408667.
Sismanis N, Pitsianis N, Sun X. Parallel search of k-nearest neighbors with synchronous operations. 2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012. 2012 Dec 1;

Published In

2012 IEEE Conference on High Performance Extreme Computing, HPEC 2012

DOI

Publication Date

December 1, 2012