5 ms·
Simpler: - Compute z-value for each vector, store in binary tree (or sorted array, etc.), keyed by z-value. - Compute z-value of search vector, search the dat
by geophile 9y ago
Simpler:
- Compute z-value for each vector, store in binary tree (or sorted array, etc.), keyed by z-value.
- Compute z-value of search vector, search the data structure, find the k adjacent items in each direction (k is small, e.g. 1-5).
- Of the vectors found, compute minimum distance from the search vector, r.
- Do another search of your data structure, using a sphere of radius r, (easy z-order algorithm).
- The nearest neighbor is the vector resulting from this search whose distance from the search vector is minimum.
- boulos 9y agoYou’ve just described a single axis kd-tree roughly. Which means you’ll also perform catastrophically for patterns with say a line in the Z-axis. It’s not that hard to do a proper spatial tree. If you hate kd-trees, an octree or a grid are also more robust than a “single axis binary split tree”.
- geophile 9y agoNot sure what you mean by a single-axis kd-tree. Z-order + sorted array/tree/etc. is a generalization of an oct-tree. An octtree is just z-order combined with a degree 8 trie. And an octtree is simply an encoding of a 3-d grid. So I really don't understand your objections. Also, I haven't tried NN search using z-order, but range searches work very well. The partitioning induced by z-order adapts well to all sorts of distributions.
- geophile 9y agoOh! I see the problem. I don't mean just a tree keyed on the z-axis. I mean z-order: https://en.wikipedia.org/wiki/Z-order https://en.wikipedia.org/wiki/Z-order
- boulos 9y agoAhh! I wasn’t sure, so sadly I chose “z as in z axis” not Z as in Z/space-filling/Hilbert/Morton order. That’s a grid in disguise! :).
- klodolph 9y agoThat's only viable when you have a small data set, which is when you don't care much about indexing to begin with.
- dvirsky 9y agoSounds like GeoHash lookup which is actually pretty robust if you have a good data structure for indexing. For example: https://redis.io/commands/georadius https://redis.io/commands/georadius
- geophile 9y agoHuh? I've used z-order inside database systems, with many millions of records. Works incredibly well.
- gmueckl 9y agoBuilding and balancing a k-d tree is not free, either. I suspect that the GP's approach is roughly the same in terms of theoretical complexity, but effectively trades memory for smaller constants and a chance to trip over edge cases like dense groups of points.