algorithm to find the nearby friends?

Question

I have a python program sitting in server side managing user location informations, each friend has a pair of (longtitude, latitude), given a (longtitude, latitude) point, how I can find the nearby(say within 5KM) friends efficiently?

I have 10K users online...

Thanks. Bin

Answer 1

New Answer:

I would store lat and long in separate columns. Place indexes on them. Then when you want to find the nearby friends of a particular user, just do something like

select field1, field1, ..., fieldn from users 
where 
    user_lat > this_lat - phi and user_lat < this_lat + phi
    and
    user_lon > this_lon - omega and user_lon < this_lon + omega

where phi and omega are the degrees of latitude and longitude that correspond to your desired distance. This will vary depending on where on the globe you are but there are established equations for figuring it out. There's also the possibility that your database can do those calculations for you.

---

old answer.

I would look at quadtrees and kd-trees.

Kd-trees would be the canonical solution here, I believe.

Answer 2

A simple way would be to sort the points along the longtitude, then, when looking up friends, find the minimum and maximum longtitudes of possible matches. Sorting the list is O(n log n), and looking up for friends is linear, but only for friends within the longtitude range. Here's an example for the case where you have all the points on a flat 2D surface:

# friends is the sorted list of (x, y) tuples, (px, py) is my location
def get_near(friends, px, py, maxdist):
    i1 = bisect.bisect_left(friends, (px - maxdist, py))
    i2 = bisect.bisect_right(friends, (px + maxdist, py))
    return [(x, y) for (x, y) in friends[i1:i2] if math.hypot(px - x, py - y) < maxdist]

For the longtitude/latitude case, you'd have to use another function for testing for distance instead of the euclidean distance(math.hypot).