Strategies for large volume of location geocoding

Question

I have an application that uses the Google Maps API to geocode distances between lat/long pairs as a way of displaying people near to you on your phone (currently Android, working on iPhone). The issue is that even with a test group of 40 users, we are taking upwards of 10 seconds to do our calculations and send the results back to the users. While 10 seconds sounds like a long time, it's not really an issue as far as the client app goes because it's not a real-time update of people's locations (the updates occur every few minutes). Obviously this is a problem though since we'd obviously love to ramp up to tens or even hundreds of thousands of users. I'm curious if anyone else has any experience in this arena in regards to using the Google Maps API for calculating distances between points for large volumes of data?

As an aside, we're using Rails on the server, which is where all of the location calculations are occurring. The phone(s) are merely displaying the maps and updating the server with lat/long coordinates.

Answer 1

You do not need the google maps API to calculate distances when you already have lat/lon coordinates. Calculating the great-circle distance can be done using haversine or vincenty formula.

Edit: If I understand your problem correctly (finding close locations to one given location in 10,000 records) I can only recommend using some geo library for this purpose. Calculating 10k distances is a bad idea when more requests are coming in. You should definitely look into smarter algorithms for that (a quad tree seems practical).

Answer 2

Take a peek at Geokit, it is a Ruby Gem and Rails plugin to do what you want and more, I think you'll be very happy with the speed and features as well.

Answer 3

You might want to considered converting lat long to a localized equidistant projection before doing any calculations if you are covering a specific area. Or more simply if covering global areas, convert the lat long to the two nearest UTM zones, storing two sets of X Y coordinates and the two UTM zones IDs. Then you can select records on UTM zone matches first, and carry out your calculations against that subset using the projected coordinates second (which will be significantly faster than calculating distance from lat long).