How does “Find Nearest Locations” work?

Question

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.,

Answer 1

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

Answer 2

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!.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.