Using k-d trees to efficiently calculate nearest neighbors in 3D vector space

Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @02:55PM (#16349220)

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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by boulos on Saturday February 10, 2018 @03:32PM (#16349419)

You’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”.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @06:01PM (#16350135)

Not 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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @07:31PM (#16350449)

Oh! 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

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by boulos on Saturday February 10, 2018 @08:21PM (#16350623)

Ahh! 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! :).

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by klodolph on Saturday February 10, 2018 @03:45PM (#16349474)

That's only viable when you have a small data set, which is when you don't care much about indexing to begin with.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @06:02PM (#16350138)

Huh? I've used z-order inside database systems, with many millions of records. Works incredibly well.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by gmueckl on Sunday February 11, 2018 @03:20AM (#16351757)

Building 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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by dvirsky on Saturday February 10, 2018 @04:36PM (#16349743)

Sounds like GeoHash lookup which is actually pretty robust if you have a good data structure for indexing. For example: https://redis.io/commands/georadius

[ Parent | on HN ]