5
$\begingroup$

I wonder if there is any study that compares the performance of kd-tree vs brute-force nearest neighbor search on GPU. Post #4 on this page suggests that kd-tree may not be the optimal algorithm for GPU but I wonder if there is any data supporting this claim?

$\endgroup$
10
$\begingroup$

Ultimately, naive brute-force KNN is an $O(n^2)$ algorithm, while kd-tree is $O(n \log n)$, so at least in theory, kd-tree will eventually win out for a large enough $n$. In practice, the leading constants for a GPU implementation may be vastly different --- we may be comparing $0.0001n^2$ vs $1000n\log n$ --- so it may indeed be the case that the former wins out for practical problem sizes.

Now, the reason for the difference in leading constants come down to parallelizability and memory access patterns. Naive KNN is embarrassingly parallelizable, and can be implemented entirely using vectorized sequential memory access. By contrast, kd-tree is naturally serial, and requires extensive conditional statements and random memory access. Algorithms like the former enjoy a massive speed-up on a GPU, while those like the latter often run slower on a GPU than a CPU.

$\endgroup$
0
$\begingroup$

Additionally to what @richard-zang said, instead of a "naive brute-force" search, you can often use some refinement, e.g. a locality-based hashing or if you have fixed neighbor distance radius, a common approach is to pre-grid/sort the search space to limit the lookup to neighboring cells (commonly used in molecular simulation and referred to as linked cell list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.