Whats the most efficient way to calculate local users from a geo coord?

Question

[edit] - as pointed out to me in the comments I should have noted that I will be using a LAMP based architecture, meaning a MySQL database. Sorry about forgetting to mention this.

I have to create a PHP backend for an iPhone app. The app sends up the users coords and requests the closes 10 local users.

I'm just wondering what is the most efficient way to determine this, I dont want to have to scan the entire table of users, calculate the distance between their geo-coords and the target & order them from lowest to farthest.

Can anyone suggest a more elegant solution instead of scanning all the users? Thanks for your time.

You didn't wrote about which database you're using. Some support this out of the box and some support it with extensions. — hakre, May 04 '11 at 23:44
Binary space partitioning may help you limit the search field. — Lightness Races in Orbit, May 04 '11 at 23:44
[GIS and Spatial Extensions with MySQL](http://dev.mysql.com/tech-resources/articles/4.1/gis-with-mysql.html); [Geo Distance Search with MySQL](http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL) — hakre, May 04 '11 at 23:58

score 1 · Accepted Answer · answered May 04 '11 at 23:50

1

You could bucket the users by approximate latitude and longitude (e.g. by whole degrees, or tenths of degrees, or whatever scale is appropriate to the distribution you've got) and then work outward from the querying user's bucket.

Not sure the extra complexity is worth it, though, unless the brute force approach is really a performance hog.

answered May 04 '11 at 23:50

David Moles

48,006
27
136
235

See also http://stackoverflow.com/questions/516574/how-can-i-do-efficient-range-searching-counting-with-latitude-longitude-data – David Moles May 04 '11 at 23:57
thanks David, maybe I'm being too cautious, brute force might suffice for the amount of users Im expecting – bennythemink Jun 13 '11 at 00:16

score 1 · Answer 2 · answered May 05 '11 at 00:36

1

The most efficient way is to use a spatial index or a space-filling-curve. A spatial index reduce the 2d complexity to a 1d complexity thus it help subdivide the surface. You want to look for Nick's spatial index quadtree hilbert curve blog.

answered May 05 '11 at 00:36

Micromega

12,486
7
35
72

sounds complicated but I will look into it, thanks for your reply epitaph – bennythemink Jun 13 '11 at 00:15
You can download my hilbert curve class at phpclasses.org (hilbert-curve). – Micromega Jun 18 '11 at 17:05

score 0 · Answer 3 · answered May 04 '11 at 23:47

0

There are multiple ways of doing this. Here is one way to do it in a sql query.

$sql = "Select id, abs($currlat - latitude) + abs($currlon - longitude) as distance from geo_loc_table order by distance asc";

The issue with this is that it is not overly efficient. I would recommend getting some form of indexing software that can do the work for you. Sphinx might be a good fit.

answered May 04 '11 at 23:47

ChrisChristensen

21
2

1

To calculate the actual difference would be more complicated then that actually. I would recommend trying Sphinx anyhow. – ChrisChristensen May 04 '11 at 23:52

score 0 · Answer 4 · answered May 05 '11 at 00:02

Due to earth curve, you must do some calculation

SELECT id, 6371 * ACos(Cos(RADIANS(users.Lat)) * Cos(RADIANS(CurrentLat)) * Cos(RADIANS(CurrentLng) - RADIANS(users.Lng)) + Sin(RADIANS(users.Lat)) * Sin(RADIANS(CurrentLat)) ) AS distance
FROM users
ORDER BY distance
LIMIT 10;

distance is in Km, if you want Miles, replace 6371 by 3959

Whats the most efficient way to calculate local users from a geo coord?

4 Answers4