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

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 2

This is a very interesting question with a complex answer.

You mention a database of cities with lat/lon, but cities are not single points and this can make a big difference in densely populated areas where large parts of city A might be closer to the "center" of city B than to the center of city A. Take a big city surrounded by smaller suburbs. The outlying parts of the big city might be closer to the centers of the suburbs than to center of the big city itself. Snapping to the nearest city center implies a map that is the Voronoi diagram of city center points. Such a map would not look anything like an actual map of urban areas.

If you want to know the city and state for a given lat/lon, you need to query a proper map and do point in polygons tests to find out which one it is in. This sounds computationally expensive, but it is actually not bad if you use a proper spatial index and are careful in your coding. I run a web site that sells API access to this and other geographical queries, and our underlying engine (written in Java) can return the containing or nearest city in the US with an average query time of 3e-4 seconds (more than 3,000 queries per second).

Even though we are selling it, I'm happy to explain how it works, since it would be way cheaper to buy it from us than to build it yourself, even with instructions. So here they are:

• Find the map that you want. For US locations, the US Census offers extremely accurate maps at: http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html. I've not found global maps that are as good as the US census maps, but they may exist.
• Find or write a parser for the ESRI shapefile format. I don't have a specific link for this, as it is highly language dependent, but there are numerous parsers, both free and commercial available on the web. Just do a search for "shapefile parser" along with your programming language.
• Load the map into memory. A digital map consists of a list of polygons represented by a list of lat/lon pairs, typically ordered in a counter clockwise direction. Most maps allow for cut-outs (e.g., Lesotho in South Africa), which are just listed as polygons where the lat/lon pairs are listed in the clockwise direction. For performance and memory consumption reasons, you will want to use raw float arrays (avoid double precision, as it wastes memory, and use native arrays where possible, to avoid boxing).
• Next, you will need code to answer whether a given query point is contained in a given polygon. Here is an excellent discussion of the point-in-polygon problem: How can I determine whether a 2D Point is within a Polygon?
• In my experience, the brute force technique suggested in another answer (checking every entity) does not work well on national or world maps. Instead, I strongly suggest a fast spatial index that returns a list of candidate polygons for a given lat/lon. Here there are a lot of options. A lot of people would suggest tree based indexes, but I tend to prefer grid indexes, as they are faster and modern servers tend to have a lot of memory. I wrote the only such index that I've worked with. I know they exist in GIS libraries, but I find most GIS code is overly complex, slow, and hard to use. So given a query lat/lon, you get a list of candidate polygons from the spatial index and use the point-in-polygon function to find which of the candidates contains the query point.
• It is also important to handle cases where the query point is not contained by any polygon. In such a case, you will presumably want to find the nearest such polygon up to a specified maximum distance. To do this, you need to make sure that your spatial index can return a list of nearby polygons, and not just a list of candidate containing polygons. You will also need code to compute the distance between a query point and a lat/lon line segment (this is hard because lat/lon is not a Euclidean space). I've not found any good discussion of how to do this online, so I devised my own method. It works by creating a linearized space around the query point (which becomes (0, 0) in the new space) in which the relative longitude is re-scaled such that a degree of the modified longitude is the same distance as a degree of latitude (involves multiplying the relative longitude by the cosine of the latitude). In this linearized space you find the nearest point on the line segment using standard methods (see Shortest distance between a point and a line segment), and then convert that point back into lat/lon and use the Haversine formula to compute the distance between the two points (see Calculate distance between two latitude-longitude points? (Haversine formula)).

And that's it. I built such a system on and off for about half a year. My estimate is that there are at least three man months of serious coding in it, and that's someone familiar with the subject matter (so beware if you are making a buy-or-build decision).