Finding users close to you while the coordinates of you and others is free to change

Question

I have a database with the current coordinates of every online user. With a push of a button the user can update his/her coordinates to update his current location (which are then sent off to server). The app will allow you to set the radius of a circle (where the user is in the center) in which you can see the other users on a map. The users outside the circle are discarded.

What is the optimal way to find the users around you?

1) The easiest solution is to find the distance between you and every user and then see if it's less than the radius. This would place the sever under unnecessarily great load as comparison has to be made with every user in the world. In addition, how would one deal with changes in the locations?

2) An improved way would be to only calculate and compare the distance with other users who have similar latitude and longitude. Again in order to be efficient, if the radius is decreased the app should only target users with even closer coordinates. This is not as easy as it sounds. If one were to walk around the North Pole with, say, 10m radius then every step around the circumference would equal to a change of 9 degrees longitude. Every step along the equator would be marginal. Still, even being very rough and assuming there aren't many users visiting the Poles I could narrow it down to some extent.

Any ideas regarding finding users close-by and how to keep them up to date would be much appreciated! :)

Andres

Answer 1

1) you would probably need a two step process here.

a) Assuming that all locations go into a database, you can do a compare at the sql level (very rough one) based on the lat & long, i.e. if you're looking for 100m distances you can safely disregard locations that differ by more than 0.01 degree in both directions. I don't think your North Pole users will mind ;) Also, don't consider this unnecessary - better do it on the server than the iPhone.

b) you can then use, for the remaining entries, a comparison formula as outlined below.

2) you can find a way to calculate distances between two coordinates here http://snipplr.com/view/2531/calculate-the-distance-between-two-coordinates-latitude-longitude/

Answer 2

Very good practice is to use GeoHash concept (http://geohash.org/) or GeoModel http://code.google.com/p/geomodel/ (better for BigTable like databases). Those are efficient ways of geospatial searches. I encourage you to read some of those at links I have provided, but in few words:

• GeoHash translates lon and lat to unique hash string, than you can query database through those hashes. If points are closer to each other similar prefix will bi longer

• GeoModel is similar to GegoHash with that difference that hashed are squares with set accuracy. If square is smaller the hash is longer.

Hope I have helped you. But decision, which you will pick, is yours :). Lukasz