What data structure would help find nearby coordinates quickly?

Question

I need to write a program that does the following:

• Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places
• Store them in a data structure once
• Provide a "nearby" lookup function that can efficiently return the N closest objects for a given lat/long

Currently, I'm doing the following, which is suboptimal:

• Store all objects in a hash, with array keys like [integer_latitude, integer_longitude]
• At search time, find all objects in an arbitrary-sized circle around the target. Eg, if the search is at [0,0], I can get all objects within 1 degree by pulling [-1,0], then [0,0], then [1,0], then [0,-1], etc.
• Order the found objects by actual distance to the target and take the top N

This is obviously inefficient, because often there are many more matches than N.

One improvement could be to examine locations in concentric squares outward from the center: all points 0 degrees from the center, all points 1 degree from the center, 2 degrees, etc, and stop after the first square when I have at least the number of objects needed. Then I could sort those by actual, fine-grained distance and take the top N.

Is there some well-established way of doing this search efficiently?

• Nathan Long: Another idea would be to use a tree of geohashes, where the geohash gets longer as you go toward the leaves. You could move to a parent to find "near" objects. But I think this fails when two objects are very close together but just opposite a boundary like the equator.
• HEKTO: Have you read this: en.wikipedia.org/wiki/Nearest_neighbor_search ?
• S.Dan: How about dictionary? Or 4 directional linked lists?
• Raphael: Closely related question; the comment applies.
• babou: I think quadtrees might give you a first approximation. They are usually good to explore some part of the plane, as a 2-dimensional counterpart to binary-trees. But I am no expert on that.

Answer 1

Yes, you could you could do better than a naive approach - you could use a k-d tree data structure.

Clever implementations, such as sklearn k-d tree do the nearest neighbour lookup in O(log(n)) which, unless you have a high dimensional and sparse dataset, will work significantly faster than a naive O(n) approach.

Answer 2

As well as k-d trees, it's worth knowing about R-trees, as these are arguably the most popular data structure for indexing in the GIS world.

R-trees are to k-d trees as B-trees are to binary search trees. Like B-trees, R-trees tend to be very cache efficient, which makes them extremely useful for on-disk data structures as you tend to find in databases.

Answer 3

There are obviously many different data structures out there - you could also use a cover tree