Fastest way to find the location(zip, city, state) given latitude/longitude.

Question

I need a free(open-source) solution that given the lat/lng can return the closet city/state or zip. mysql is not an option, a small lightweight database would be the best if possible.

Updates: No web services, with 50 million impressions a day even the smallest addon hurts so adding a service request would kill response time. I would prefer not to add more than 200 milliseconds on to the request.

I have the database, lat/lon/zip/city/state in csv it's just how to store and more importantly how to retrieve it the quickest.

Answer 1

Its not open-source but maybe you could use the Google Maps API:

Reverse Geocoding

Answer 2

Another thread recommends mod_geoip via MaxMind. It runs at the Apache level, before it even gets to the PHP/.NET/Java. http://stackoverflow.com/questions/593401/maxmind-geolocation-apis-apache-vs-php

Answer 3

If you have both the long and the lat for the zip and the current location you could just calculate a radius and find the points within that circle. If you make an assumed boundry of each zipcode range you could speed up the search.

If you can use SQL 2008 (standard or express) you could use Spatial data types.

Answer 4

Brute force: pre-load all of your data into an array. Calculate the distance between your current point and each point in the array (there's a method to do this calculation that uses linear algebra instead of trig functions, but I don't recall what it is offhand) to find the closest point.

Please read this before down-voting: there are ways to speed up a brute force search like this, but I've found that they're usually not worth the trouble. Not only have I used this approach before to find nearest zip from latitude/longitude, I've used it in a Windows Mobile application (where the processing power is not exactly overwhelming) and still achieved sub-second search times. As long as you avoid the use of trig functions, this is not an expensive process.

Update: you can speed up the search time by apportioning your zip data into sub-regions (quadrants, for example, like northwest, southeast etc.) and saving the region ID with each data point. In the search, then, you first determine what region your current location is in, and compare only to those data points.

To avoid boundary errors (like when your current location is near the edge of its region but is actually closest to a zip in the neighboring region), your regions should overlap to some extent. This means some of your zip records will be duplicated, so your overall dataset will be a bit larger.

Answer 5

The Yahoo! Placemaker is a free web service that can do this. It can look up place names (“New York City”, “Buckingham Palace”) but it can also look up latitudes and longitudes by using the Geo microformat.

To use the service, you submit a POST request, and it returns XML:

A small command-line example (I’ve obscured my Yahoo! app ID; you’ll need to register your own):

$ curl -X POST -ddocumentContent='<div class="geo">GEO: <span class="latitude">37.386013</span>, <span class="longitude">-122.082932</span></div>' -ddocumentType='text/html' -dappid='your_yahoo_app_id' http://wherein.yahooapis.com/v1/document

This returns a very detailed XML document, part of which is:

<type>Town</type>
<name><![CDATA[Los Altos, CA, US]]></name>

It also contains the following data:

<type>Zip</type>
<name><![CDATA[94024, Los Altos, CA, US]]></name>

I have not used Placemaker very much, but I have used their Geocoding API and it is very fast. Couple this with a local memcached and users have no idea the data isn’t local.

Answer 6

you should check out geonames. they have an API that returns XML and/or JSON. also, you can dl their database.

Answer 7

Look at the geonames.org database for source data.

For a light database, sqlite is a good choice.

geonames also does a webservice, but if you want to do it yourself without a web call (and it sounds as though you do) then you will need a local database. Then, you just need to do the right trig calculations to work out the great circle distance (google that) between a pair of lat / lng points and then order the results by distance. You can also use a bounding box or radius, if you want to limit the search radius before doing the calculations.

If your local database can be SQL based (which sqllite3 is) then that all adds up to a SQL query which adds a bunch of trig calculations to calculate a 'distance' column and maybe also a similar 'where' clause to limit the search within a radius or bounding box. Having calculated the distance column in your query then it is easy to order by distance and add any other criteria you like. If you know ruby/rails and want to see a nice example of how this is done, look at the GeoKit rails plugin source.

Answer 8

Use a kd-tree to speed up the nearest-neighbor search. There should be lots of free implementations available whatever your platform is.

Answer 9

How far from your source location would you expect the closest city to be? 50 miles? 200 miles? 500 miles? If two cities are nearly equidistant, does it matter if your algorithm picks the exactly closer one? You can use this information to help speed your search.

If you can reasonably assume that the distance difference is small (~250 mi or so is probably close enough to be considered 'small'), and your distance calculation can be a bit 'fuzzy', then you can optimize the 'brute force' check by limiting your search space to +/- 5 lat from the source (~70 miles per lat, so this gives you 350 or so miles to the north and south), and +/- 5 long (presuming you aren't searching for cities at the poles, this is anywhere from ~350 mi at the equator to ~100 mi in northern Canada). Adjust these ranges to what you feel is appropriate for your problem space.

While trig functions will help give you a precise indication of distance, for smaller distances such as these Pythagorean is generally close enough for a 'best guess' answer, with x = 69.1 * (sourcelat - citylat) and y = 53.0 * (sourcelong - citylong).