most efficient way of calculating nearest city (from whitelist)

I have a whitelist of cities. Let's say, Seattle, Portland, Salem. Using GeoIP, I'd detect user city. Let's call it $user_city. Based on $user_city, I want to display classified-listings from nearest city from my whitelist (Seattle || Portland || Salem) with in 140 miles. If city is not listed in 140 miles, I'd just show a drop-down and ask user to manually select a city.

There are a few ways of doing thi开发者_运维百科s:

1. calculate this on the fly (I found an algorithm in one of SO answers)
2. with help of DB (let me explain):

create a table called regions

regions will have

city 1 | city 2 | distance (upto 140 miles)

city 1= cities from whitelist

city 2= any city within 140 miles from city 1

This would create a reasonable sized table. If my whitelist has 200 cities, and there are 40 cities (or towns) within 140 miles of each city. This would create 8000 rows.

Now, when a user comes to my site:
1) I check if user is from whitelist city already (city 1 column). If so, display that city
2). If not, check if $user_city is in "city 2" column
 2a) if it is, get whitelist city with lowest distance
 2b) if it is not, display drop-down for manual input

Final constraint: whichever method we select, it has to work from within iFrame. I mean, can I create this page on my mysite1.com and embed this page inside someothersite2.com inside an iframe? Will it still be able to get user_city and find nearest whitelisted city? I know there are some cross-domain scripting rules so I am not sure if iFrame would be able to get user-ip address, pass it to GeoIP, and resolve it to $user_city

So, my question:

How best to do this? If a lot of people embed my page in their page (using iframe) then my server would get pounded 10000s of times per second (wishful thinking, but let's assume that's the case). I don't know if a DB would be able to handle so much pounding. I don't want to have to pay for more DB servers or web-servers. I want to minimize resource-requirement at my end. So, I don't mind offloading a bit of work to user's browser via JavaScript.

EDIT:

1. Some answers have recommended storing lat, long and then doing the Math. The reason I suggested creating a 'regions' table is that this way all math is precomputed. If I have a "whitelist" of cities, and if I precompute all possible nearby city for each whitelisted city. Then I don't have to compute distance (using Haversine algorithm for eg) everytime.

2. Is it possible to offload all of this to user's browser via some crafty use of Java Script? I don't want to overload my server for a free service. It might make money but I am very close to broke and I am afraid my server would go down before I make enough money to pay for the upgrades.

So, the three constraints of this problem are 1) should work from inside iframe (I am hoping this will go viral and every blogger would want to embed my site into their page's iframe. 2) should be very fast 3) should minimize load on my server

• Use one table City and do a mysql math-calculation for every query, with the addition of a cache layer eg memcache. Fair performance and very flexible!
• Use two tables City (id,lat,lng,name) and Distance (city_id1,city_id2,dist), get your result by a traditional JOIN. (Could use a cache layer too.) Not very flexible.
• Custom data structure: CityObj (id,lat,lng,data[blob]) just serialize and compress a php-array of the cities and store it. This might rise your eyebrows but as we know the bottleneck is never CPU or memory, it's disc IO. This is one read from an index of an INT as apposed to the JOIN which uses a tmp-table. This is not very flexible but will be fast and scalable. Easy to shard and cluster.

Is it possible to offload all of this to user's browser via some crafty use of Java Script? I don't want to overload my server for a free service. It might make money but I am very close to broke and I am afraid my server would go down before I make enough money to pay for the upgrades.

Yes, it is possible...using Google Maps API and the geometry library. The function you are looking for is google.maps.geometry.spherical.computeDistanceBetween. Here is an example that I made a while ago that might help get you started. I use jQuery here. Take a look at the source to see what's happening and modify as needed. Briefly:

1. supplierZips is an Array of zip codes comparable to your city whitelist.
2. The first thing I do on page load is geocode the whitelist locations. You can actually do this ahead of time and cache the results, if your city whitelist is constant. This'll speed up your app.
3. When the user enters a zip code, I first check if it's a valid zip from a json dataset of all valid zip codes in the U.S.( http://ampersand.no.de/maps/validUSpostalCodes.json, 352 kb, data generated from zip code data at http://www.geonames.org).
4. If the zip is valid, I compute the location between that zip and each location in the whitelist, using the aforementioned computeDistanceBetween in the Google Maps API.

Hope this helps get you started.

You just have to get the lat and the long of each city and add it to the database.

So every city only has 1 record. No distances are stored on the position on the globe.

Once you have that you can easily do a query with using haversine formula ( http://en.wikipedia.org/wiki/Haversine_formula ) to get the nearest cities within a range.

know there are some cross-domain scripting rules so I am not sure if iFrame would be able to get user-ip address

It will be possible to get the user ip or whatever if you just get the info from the embedded page.

I don't know if a DB would be able to handle so much pounding

If you have that many requests you should have by then found a way to make a buck with it :-) which you can use for upgrades :D

Your algorithm seems generally correct. What I would do is use PostGIS (a postgresql plugin, and easier to set up than it looks :-D). I believe the additional learning curve is totally worth it, it is THE standard for geodata.

If you put the whitelist cities in as POINTs, with latitudes and longitudes, you can actually ask PostGIS to sort by distance to a given lat/lon. It should be much more efficient than doing it yourself (PostGIS is very optimized).

You could get lats and longs of your user cities (and the whitelist cities) by using a geocoding API like Yahoo Placefinder or Google Maps. What I would do would be to have a table (either the same as the whitelist cities or not) that stores city name, lat, and lon, and do lookups on that. If the city name isn't found though, hit the API you are using, and cache the result in the table. This way you'll quickly not need to hit the API except for obscure places. The API is fast too.

If you're really going to be seeing that kind of server load, you may want to look into using something besides PHP though (such as node.js). Incidentally you shouldn't have any trouble geocoding from an iframe, from the Point of View of the server, its just like the browser is going to that page "normally".