What data structure would help find nearby coordinates quickly? 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?
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.