K-Nearest Neigbors and Radius (Range) Search
Filed under: Algorithms, Computational Geometry, Mathematics
BruteSearchMex
When the dataset is small, when you have to run only a few number of search, or when the dimensions of points is large, the brute search method is still faster than kd-trees data structure. Computing the distances one by one take a minor time than building the tree.
Some of this problems have became less gravous since the introduction of GLTree (file id 22190) which allows for a very fast tree construction.
Despite this, very small dataset are still terrain for brute search algorithms.
I saw many k-neighbours utilities on FEX, but all them were m-coded. I think such a brute calculation is not an m-code job. So I developed my own Nearest Neighbour finder. It is nothing special it just computes all the distances and take the ones required from the input parameters, but of course the mex implementation make it even faster than vectorized m-code.
The following utilities are provided:
- Nearest neighbor
- K-Nearest neighbors
- Radius Search
They al supports N-dimensions and work on double, it is possible to choose if return the distances.
Here is a time comparison with a vectrized m-code:
Output:
Elapsed time is 0.962640 seconds.
Elapsed time is 18.813100 seconds.
For info, questions, suggestions, bugs: giaccariluigi@msn.com
Download Now
Popularity: 42% [?]
Translator
By N2H Follow Us
Video Posts
-
