4

Say you have a list of gps coordinates for every restaurant on earth, and you have the coordinates for your current location. You want to find the closest n restaurants. Obviously it could take forever to search through an unsorted list, they need to be indexed somehow.

How should they be stored/indexed to be able to find the closest ones easily? I was thinking some kind of a double dictionary by latitude and longtitude or a double hash of some kind, but I'm sure this problem has been tackled before, and I'm wondering if there's an "optimal" solution.

NathanTempelman
  • 1,301
  • 9
  • 34

3 Answers3

3

I believe a KD-Tree is the general approach to these queries.

Wikipedia entry on KD-Tree.

Nearest neighbor search info on Wikipedia.

Previous question on SO about NNS.

Implementations:

PCL

KdTree in Java

Community
  • 1
  • 1
Justin
  • 4,196
  • 4
  • 24
  • 48
  • That looks promising, although I'm wondering if there wouldn't be a better way to do it for gps, seeing as the locations wouldn't be distributed throughout a 3d space, but on the 2d surface of a sphere. Thoughts? – NathanTempelman Oct 28 '13 at 20:21
  • @NathanTempelman Well, from what I know about KD-Trees, they perform better with less dimensions. But I am not expect in the NNS space, so there may be better data-structures. – Justin Oct 28 '13 at 20:27
  • @NathanTempelman I've added a new link to a previous NNS question on SO. – Justin Oct 28 '13 at 20:34
  • 1
    Given the sparsity of restaurants in high latitudes, using a 2D kd-tree to represent those parts of the surface of the Earth of practical interest is a reasonable approach. – High Performance Mark Oct 28 '13 at 20:37
2

You can use a quadtree, especially a quadkey. It can be very efficient because you can change the gridsize. There are also many different quadkeys, for example morton curve, hilbert curve, h-tree, moore curve.

Micromega
  • 12,486
  • 7
  • 35
  • 72
0

If you are looking for a KDTree implementation in Java or Android, see my answer to a similar SO-question following this link. I posted also a 2D implementation in the same SO question, but this may return wrong results, if the points are distributed across a great range of latitudes. (An absolute distance in longitude degrees translates into a whole range of possible east-west distance in meters depending on the latitude). I am still using the 2D-algorithm, as I am only interested in waypoints in less than 1000 meter distance. And there the 2D version worked fine so far.

Community
  • 1
  • 1
user2808624
  • 2,502
  • 14
  • 28