NearptD: A Parallel Implementation of Exact Nearest Neighbor Search using a Uniform Grid

We present NearptD, a very fast parallel nearest neighbor algorithm and implementation, which has processed 10M points in E6 and 184M6 points in E3. It uses 1/5 the space and as little as 1/100 the preprocessing time FLANN (a well-known approximate nearest neighbor 4program). Up to E4, its query time is also faster, by up to a factor of 100. NearptD uses Nvidia Thrust and CUDA in C++ to perform parallel preprocessing and querying of large point cloud data. Nearest neighbor searching is needed by many applications, such as collision detection, computer vision or machine learning. This implementation is an extension of the Nearpt3 algorithm performed in parallel on the GPU for a variable number of dimensions. NearptD shows that a uniform grid can outperform a kd-tree for preprocessing and searching large datasets.