How does “Find Nearest Locations” work?

问题:

Nowadays most of the Restaurants and other businesses have a "Find Locations" functionality on their websites which lists nearest locations for a given address/Zip. How is this implemented? Matching the zipcode against the DB is a simple no-brainer way to do but may not always work, for example there may be a branch closer to the given location but could be in a different zip. One approach that comes to my mind is to convert the given zip-code/address into map co-ordinates and list any branches falling into a pre-defined radius. I welcome your thoughts on how this would've been implemented.If possible provide more detailed implementation details like any web-services used etc.,

回答1:

A lot of geospatial frameworks will help you out with this. In the geospatial world, a zip code is just a "polygon", which is just an area on a map which defines clear boundaries (not a polygon in the math sense). In SQL 2008 spatial, for example, you can create a new polygon based on your original polygon. So you can dynamically create a polygon that is your zip code extended by a certain distance at every point. It takes the funky shape of the zip code into account. With an address, It’s easy, because you just create a polygon, which is a circle around the one point. You can then do queries give you all points within the new polygon that you created in either method.

A lot of these sites are basically just doing this. They give you all points within a 5 mile extended polygon, and then maybe a 10 mile extended polygon, and so on and so forth. They are not actually calculating distance. Most ma stuff on the web is not sophisticated at all.

You can see some basic examples here to get the general idea of what I'm talking about.

回答2:

There is a standard zipode/location database available. Here is one version in Access format that includes the lat/long of the zipcode as well as other information. You can then use The PostgreSQL GIS extensions to do searches on the locations for example.

(assuming of course that you extract the access db and insert into a more friendly database like PostgreSQL)

回答3:

First, you Geocode the address, translating it into (usually) a latitude and longitude. Then, you do a nearest-neighbour query on your database for points of interest.

Most spatial indexes don't directly support nearest-neighbour queries, so the usual approach here is to query on a bounding box of a reasonable size with the geocoded point at the center, then sort the results in memory to pick the closest ones.

回答4:

Just like you said. Convert an address/ZIP into a 2D world coordinate and compare it to other known locations. Pick the nearest. :) I think some DB's (Oracle, MSSQL 2008) even offer some functions that can help, but I've never used them.

回答5:

I think it is pretty universal. They take the address or zipcode and turn it in to a "map coordinate" (differs depending on implementation, probably a lat/long) and then using the "map coordinates" of the things in the database it is easy to calculate a distance.

Note that some poor implementations convert the zipcode in to a coordinate representing the center of the zipcode area, which sometimes gives bad results.

回答6:

Your thoughts on how to do it are how I would probably do it. You can geocode the co-oridinated for the zip and then do calculations based on that. I know SQL Server 2008 has some special new functionality to help doing queries based on these geocoded lon/lat co-ordinates.

回答7:

There are actual geometric algorithms and/or datastructures that support lower O(...) nearest location queries on point, line and/or region data.

See this book as an example of information on some of them, like: Voronoi diagrams, quadtrees, etc.

However I think the other answers here are right in most cases that you find in software today:

1. geocode (a single point in) the search area
2. bounding box query to get an initial ballpark
3. in memory sorting/selecting

回答8:

I had table that i would compile a database table every 6months it contained 3 columns, I used it for a few clients in Australia, it contained about 40k of rows, very lightweight to run a query. this is quite quick, if just looking to get something off the ground for a client

1. Postal Code from
2. Postal Code To

3. Distance

   SELECT Store_ID, Store_AccountName, Store_PostalCode, Store_Address, Store_Suburb, Store_Phone, Store_State, Code_Distance FROM Store, (SELECT Code_To As Code_To, Code_Distance FROM Code WHERE Code_From = @PostalCode UNION ALL SELECT Code_From As Code_To, Code_Distance FROM Code WHERE Code_To = @PostalCode UNION ALL SELECT @PostalCode As Code_To, 0 As Code_Distance) As Code WHERE Store_PostalCode = Code_To AND Code_Distance <= @Distance ORDER BY Code_Distance

There may be plenty optimization that you could do to speed up this query!.