Multicore Construction of k-D Trees for High Dimensional Point Data

Proc. Advances in Big Data Analytics, July 2014

This paper presents the first parallelization of FLANN’s k-d tree for approximate nearest neighbor finding of high dimensional data. We propose a simple node-parallel strategy that acheives surprisingly scalable speedups on a range of inputs and hardware platforms. When combined with speedups from SIMD vectorization, our approach can achieve up to 91x total speedup over the existing FLANN implementation on a 32-core machine.

AttachmentSize
kdtree-abda.pdf711.54 KB

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer