How to implement an app that brings Location Based deals to your phone?

Savvy shoppers have always been on the lookout for new deals, but sites such as Groupon, Gilt City, and LivingSocial have made deal-hunting even more popular.By aggregating local deals from these sources, it would make them less intrusive (than email alerts) and easy to peruse.

How do I find the deals?
The first step is to know where the deals are. We can get a list of cities (either through API calls to the deal sites or RSS feeds provided by them) and store the longitude and latitude of these cities. If the sites are unable to provide a list of cities and/or their coordinates, it is relatively straightforward to scrape the list of cities from their website (with permission of course!) and find the coordinates of the cities through services such as the Google Geocoding API.  Once we have this data, we store the city/coordinate pairs in the Google AppEngine datastore.

My Location?
On GPS enabled devices, location coordinates are relatively easy to come by. A client application can simply query the server with a user’s coordinates (with user’s permission) using an API call such as:http://<server>/api/nearby?long=-73&lat=42&max=10. After some server-side calculations, this call will return a list of nearby cities that should be relevant to the user because they are nearby the location the user just provided.

What is nearby?

Given that we have each city’s coordinates stored on the server and the user’s coordinates from the client application, how do we determine which cities are closest? We use the following algorithm to figure out which cities we should show to the user:

for city in cities:
    dist = math.pow(city.long - user.long, 2) + math.pow(city.lat - user.lat, 2)
    heapq.heappush(result, (dist, city))

The result is a min heap that ranks the cities from the closest to the farthest. We return this list (or a subset of it) to the client application and then allow the user to choose to add deals from a city near them.

The key to making this operation efficient is loading the city coordinates into memory (in our case, into the AppEngineMemcache). This simple optimization works well for any small/medium sized list of locations and turns a resource intensive calculation (that can be quite involved to implement on AppEngine’s datastore) into simple and scaleable operation that requires no datastore calls.