Parallel Search of k-Nearest Neighbors with Synchronous Operations
Department of Electrical and Computer Engineering, Aristotle University, Thessaloniki, Greece
IEEE High Performance Extreme Computing Conference(HPEC ’12), 2012
@article{sismanis2012parallel,
title={Parallel Search of k-Nearest Neighbors with Synchronous Operations},
author={Sismanis, N. and Pitsianis, N. and Sun, X.},
year={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.
November 19, 2012 by hgpu
