Location based search

Question

We currently have a site where objects can be searched for by location. We have a search box and a dropdown of states in our country. Each object has a relationship with one state.

We would like to expand this website into other countries. Our choices appear to be:

1/ For each country we want to go in to, we need a list of states and possibly post codes. The objects are associated with states and postcodes and a dropdown is provided alongside the search box.

2/ Associate a longitude and latitude to each object and have google api return a longitude and latitude for the address a user types when they search. Then find the objects which fall within a certain radius of the long/lat of the searched address.

Option 1 would perform well but is limited because we have to do a lot of work before entering each country (getting list of states/postcodes).

Option 2 seems like the most elastic and there would be no limit on going in to a new country. However, it would probably perform poorly if not done well. How would you avoid searching all objects in the table to find out of there long/lat falls withing the radius of the long/lat of the searched address?

We like how www.skillpages.com works. Very quick and accurate search and this is something we would like to replicate if we choose option 2.

Any advice on how best to create an accurate and elastic location based searching algoritm would be greatly appreciated.

Answer 1

Option 2 sounds like the best option if you want to allow users to search for items within x miles radius. There shouldn't be much database overhead if you setup indexed columns storing the lat/lng of each item

Assuming PHP/MySQL based something like:

$radius = 0.15; // Would be calculated based on radius of the search
$user_lat = -0.134239; // Latitude of User Searching
$user_lon = 51.510238; // Longitude of User Searching

$query = mysql_query("SELECT * FROM `items` WHERE `lng`<'". ($user_lon + $radius) ."' AND `lng`>'". ($user_lon - $radius) ."' AND `lat`>'". ($user_lat - $radius) ."' AND `lat`<'". ($user_lat + $radius) ."'");

Answer 2

Consider dividing the country into regions , sub regions , cities , locality . As many levels as optimum . Instead of running the api request in real time , store distances between localities in a city (say a city has 100 localities , this would result in a 100 X100 locality matrix/table for ONE city) .

Depending on what user enters as locality display results accordingly , all results in a city perhaps ORDERED BY distance between the user's locality and all other localities . Kind of like changing the city center to user's location .

However this would result in individual 'location tables' for cities , if you go beyond some number of cities I can only speculate the problems that would creep in .

I am trying to do the same for my website .

Considering if storing the distance data in XML or bitmaps (these are used a lot for creating social graphs on social networking websites) would save performance .

Depending on number of users, a real time call to the api + calculation of distance should cost a lot of time . Anyway google api calls are limited as well .