Algorithm for finding close friends?

Question

I have a python program sitting on the server side that controls the user's location information, each friend has a pair (longitude, latitude), a given point (longitude, latitude), how can I find nearby friends (say, at 5KM) effectively?

I have 10K users online ...

Thanks. Bin

Answer 1

New answer:

I would keep lat and long in separate columns. Place pointers on them. Then, when you want to find close friends of a specific 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 degrees of latitude and longitude corresponding to your desired distance. This will vary depending on where you are on the globe, but there are established equations for determining it. It is also possible that your database can perform these calculations for you.

---

old answer.

I would look at quadtrees and kd-trees .

Kd trees would be, in my opinion, a canonical solution.

Answer 2

A simple way would be to sort the points along the longitude, and then, when searching for friends, find the minimum and maximum longitude of possible matches. Sorting the list is O (n log n), and searching for friends is linear, but only for friends in the longitude range. Here is an example for the case when you have all the points on a flat two-dimensional 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 case of longitude / latitude, you will need to use another function to check the distance instead of the Euclidean distance (math.hypot).

Answer 3

Make a dict {graticule: [users]} ("graticule" is a 1 degree x 1 degree longitude block, so you can just round the values). To find nearby users, first get users from the same and neighboring graticules (since the target may be close to the edge), and then filter them using a basic test with a bounding box (i.e. what is the minimum longitude / latitude that are possible for someone within the desired radius), then do a detailed test (if you need accuracy, then you will use more complex math than just Pythagoras).

Answer 4

http://www.movable-type.co.uk/scripts/latlong.html in terms of efficiency, the only thing that really comes to mind is a preliminary calculation of the distance as you make entries in the database, that is, another table, which stores a pair of locations along with the distance, for each location added at the time it was added, you bear the cost of calculating the distance to each point in the system, and then searching this table can quickly resolve the location at a specific distance.

The answer to Aaronasterling seems to be that I tried to think it out myself, but did not know that it exists :) so this is probably the best solution, but I'm sure you will incur something overhead in the search time using this algorithm ( although it’s probably small, since in the general case the intersection of a tree as long as it is reasonably balanced is usually a fairly quick process, and it will take me some time to understand how the tree is composed, but for me this is a new concept) .