Possible to calculate closest locations via lat/long in better than O(n) time?

Question

I'm wondering if there is an algorithm for calculating the nearest locations (represented by lat/long) in better than O(n) time.

I know I could use the Haversine formula to get the distance from the reference point to each location and sort ASC, but this is inefficient for large data sets.

How does the MySQL DISTANCE() function perform? I'm guessing O(n)?

Answer 1

If you use a kd-tree to store your points, you can do this in O(log n) time (expected) or O(sqrt(n)) worst case.

Answer 2

You mention MySql, but there are some pretty sophisticated spatial features in SQL Server 2008 including a geography data type. There's some information out there about doing the types of things you are asking about. I don't know spatial well enough to talk about perf. but I doubt there is a bounded time algorithm to do what you're asking, but you might be able to do some fast set operations on locations.