On: Using k-d trees to efficiently calculate nearest n...

[klodolph]

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

[geophile → klodolph]

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

[gmueckl → klodolph]

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.

[dvirsky → klodolph]

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