kdtree for geospatial point search

Question

I'm attempting to find nearest neighbors for point geometry with latitude and longitude information available to me. After much search I concluded that using a kd-tree based approach would be the best option. I have so far tried three different approaches with kd-tree, none of which have worked.

1. Using mercator (UTM) projections. This was least useful as the distance calculation turned out to be completely wrong particularly since the points are spread all over the globe.

2. Using latitude and longitude system of co-ordinates itself. KdTree alternates between lat and long for splitting plane. This has an inherent problem, in that the latitude are parallel and hence equidistant, but longitudes aren't. So computing the distance from the splitting plane is a function of latitude. But splitting plane by definition carries only one dimension - the one on which it splits.

3. Using cartesian co-ordinates by converting lat-long to xyz. The cartesian co-ordinates do not result in the same nearest neighbors as the distance computed using lat-longs. Points closely spaced on xyz plane turned out to be farther off on lat-long plane and vice-versa.

Does anyone know of a different approach to this problem and one that works? Many Thanks!

Edit: I was wrong about the third approach. It actually works quite well.

Answer 1

I have successfully implemented a mercator projection and a quadkey. Convert the x-and y co-ordinate to a binary and interleave it. Then treat it as a base-4 number.