A Mixed Hierarchical Algorithm for Nearest Neighbor Search

Carlo del Mundo, Mariam Umar
Virginia Tech, 2202 Kraft Dr., Knowledge Works II Building, Blacksburg, VA
Advanced Parallel Computation (CS 5234) class project, Blacksburg, VA, USA, 2013


   title={A Mixed Hierarchical Algorithm for Nearest Neighbor Search},

   author={del Mundo, Carlo and Umar, Mariam},



Download Download (PDF)   View View   Source Source   



The k nearest neighbor (kNN) search is a computationally intensive application critical to fields such as image processing, statistics, and biology. Recent works have demonstrated the efficacy of k-d tree based implementations on multi-core CPUs. It is unclear, however, whether such tree based implementations are amenable for execution in high-density processors typified today by the graphics processing unit (GPU). This work seeks to map and optimize kNN to massively parallel architectures such as the GPU. Our approach synthesizes a clustering technique, k-means, with traditional brute force methods to prune the search space while taking advantage of data-parallel execution of kNN on the GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: