Large volume geocoding and distance checking

Question

I am trying to write an app for a company that maintains a registry that is updated everyday. The app will have to take the user's location and display all the nearest locations that are in that registry. Thus far I have gotten the app to call out to google and get geocoding information for a small Plist that I came up with. However, considering it from a scaled up point of view....I am using one geocoding key right now and this app cannot work correctly and quickly in the real world because google only give 15000 request per day per key.. and the list is located on the company's server. This is a big list. upwards of 25000 data points.

How do these guys like the "Yowza" app or any other location based app search through these data bases that get updated often while getting the geocoding information they need for all users. Do they store the lats and longs for given locations or do I need something special from Google? And how do they get the information so fast. Does the implementation of the SQLite data base help with this? Thank You in advance.

Answer 1

Google has I don't know how many servers. They can be really fast with that.

If your application needs a lot of time-sensitive user data, available across the entire network, I really don't know of another way to do it except to send updates from everywhere to your DB server. And if it needs to be zippy, then you need a lot of muscle, some really clever coding, or both.

Then, if you need to find users that are nearby, then you can, I suppose, return all users that are within a certain latitude/longitude window.

Answer 2

If it isn't too late to select your database engine, SQL Server 2008 now has features to allow you to work with spatial data. You can do things like distance calculations in T-SQL. There is a pretty nice article about working with spatial data through SQL Server 2008 here.

Answer 3

Can you clarify where you're doing the geocoding? Are your 25k data points changing every day, or are you thinking that you are going to have enough iPhone users to hit the 15k limit every day? Also, are you trying to get latitude and longitude from an address, or an address from latitude an longitude?

If all you're doing is displaying the top XX nearest locations, then you won't have to do any geocoding from the iPhone. You can get the current latitude and longitude from Core Location. Then you can compare that location with your database to figure out what's closest. If your database supports GIS/spatial functions (most do), then use them. If not, roll your own (trigonometry is your friend).

If you really know that you're going to hit the limit, then consider caching the geocoding data. That way you can first check if it (the iPhone or the 'registry' location) how far away you are from a cached location. If you're close enough to the cached location (maybe 1/4 mile, depends on what these things are), then use the cached results. Only do the geocoding if you're too far away.

Answer 4

If your locations are static and you just need to know how far the user is from one of the locations you can use this snippet(sorry it's so sloppy):

- (CLLocationDistance)distanceToLocation: (CLLocationCoordinate2D)theLocation
{   
    CLLocationCoordinate2D location1 = [[locationManager location] coordinate];   
    CLLocationCoordinate2D location2 = theLocation;

    typedef double KLLocationRadians;

    //////////
    const double DEGREES_TO_RADIANS = 0.0174532925;
    CLLocationDistance R = 6371; // mean radius of the earth in km
    CLLocationDegrees dLat = (location2.latitude - location1.latitude);
    CLLocationDegrees dLon = (location2.longitude - location1.longitude);
    KLLocationRadians dLatRadians = dLat * DEGREES_TO_RADIANS;
    KLLocationRadians dLonRadians = dLon * DEGREES_TO_RADIANS;

    double sinDLatRadiansOver2Squared = sin( dLatRadians / 2.0 ) * sin( dLatRadians / 2.0 );
    double cosLocation1InRadiansTimeCosLocation2InRadians = 
    cos( location1.latitude * DEGREES_TO_RADIANS ) * cos( location2.latitude * DEGREES_TO_RADIANS );
    double sinDLonRadiansOver2Squared = (sin( dLonRadians / 2.0 ) * sin( dLonRadians / 2.0 ));

    double a = sinDLatRadiansOver2Squared + (cosLocation1InRadiansTimeCosLocation2InRadians * sinDLonRadiansOver2Squared);

    double c = 2.0 * atan2( sqrt( a ), sqrt( 1 - a ) );
    CLLocationDistance distance = R * c;
    //NSLog( @"Distance is: %.2fkm - %.2fmiles", distance, (distance * 0.621371192) );

    return (distance * 0.621371192); // return distance in miles
}

Also, you could create two CLLocation objects and use the distanceToLocation: method.

Answer 5

This server side list should already provide lat/long coordinates for all data points. If it doesn't have them now, start converting today using your 1500 Google conversions per day. Then you are simply doing spatial queries on the server side to find points local to the user and laying them out on the map.

25k data points is honestly not that much though, you could store them locally in the app and have the app query for new data points. There's also a spatial variant of sqllite you could use to try and do device local spatial queries.

Answer 6

Makinitez21,

if you only have about 25,000 records that you need geocoded then you could simply do it over a couple of days using googles webservice. However, incase your DB is a lot larger then your only option is to look for a service that does not have any limitation in terms of max records. There are a couple of geocoding apps (geocoder.us and bulkgeocoder.com) where you can supply a data file and get it geocoded. This can then be imported directly back into your DB.

Jack