3 ms·
A few years ago I had to create a nearest neighbour lookup algorithm that had to perform 2D searches in a microsecond with 16 million points (k-d trees and the
by davidjohnstone 12y ago
A few years ago I had to create a nearest neighbour lookup algorithm that had to perform 2D searches in a microsecond with 16 million points (k-d trees and the like didn't cut it).
I spent a lot of time reading books and papers on computational geometry. I had an idea that involved a few minutes of precomputing things, and eventually came across a useful algorithm in a paper that let me implement this as I envisaged. In the end, everything worked perfectly. It was very satisfying.
- notimetorelax 12y agoThat sounds very interesting. If you don't mind could share the algorithm name?
- sillysaurus3 12y agoDo you happen to remember the paper? If so, would you link to the PDF? It sounds really cool!
- davidjohnstone 12y agoThe paper was only an algorithm for part of this — I can't remember the paper, but it gave an algorithm to find all of the closest points to a line. How my algorithm worked was to break the search space into a 2D array of much smaller squares. In the initialisation phase I put the points in each square that are closest to any search point in that square (some points were in multiple squares). Therefore, when a search was run, the square the search point falls in is looked up, and the list of twenty or so points was looked through for the closest point in a slightly optimised way (no square roots here).
- cmp0 12y agoSounds like an R* tree or some variant of that?