Filter by Proximity, Sort by Most Recent
This post is about a user interface pattern, a common use case for it and an example implementation. The pattern is adding an extra dimension to a timeline. The use case is showing results that are both recent and nearby. The example implementation uses a slider widget and an adequate-result-volume algorithm.
When you have 1000 messages and you want to prioritise the best 50 to display, sort is the most common pattern. If the user is interested in the latest messages, sort by most recent. If they want to see the messages other users found interesting, sort by a metric like views or rating. However, the web is increasingly about real time data. Developers are processing streams and modelling tubes instead of tables. It rarely makes sense to display real time data in any order apart from most recent. So, what do you do when you want to prioritise by another dimension, like proximity or rating?
You apply a filter. In the case of a discrete filter like a keyword or tag, this is relatively simple. The user types #architecture into the search input and Twitter obliges. However, in the case of a range filter like rating or proximity it’s not quite so simple. The user types near:london and Twitter, once again obliges. The subtle difference is that, in this case, Twitter makes an assumption for the user. It applies a default radius (aka default range). "Near" actually means "within 15 miles".
Compare the result volume of near:london with the result volume of near:abergavenny. In the first case (London) the result volume is so high, I may well prefer “near” to be more focused; perhaps meaning a radius of 5 miles. In the second, the result volume is so low I may prefer to widen the search to yield more recent results. Had I chosen somewhere really remote, would there have been any recent tweets at all?
Guessing a default radius introduces the risk of a bad user experience, whether through noisy results or a dead end. This can be avoided with an algorithm that prescribes the desired result volume and varies the radius or range. Let’s walk through a concrete example, written in Python and CoffeeScript using SQLAlchemy and a spatially enabled SQL database.
(Before I do, let me note that this implementation was inspired by Tav’s work on the original Placestation website, where he designed, implemented and introduced me to the algorithm. I am just the messenger.)
The following gist provides example code showing how to store and query geolocated Messages. Note that the location is stored as a Geography Type. This allows us to use a latlng projection (SRID 4326) whilst still accurately querying for results within a distance provided in metres. (If you’re not familiar with map projections, it’s worth getting your head around them before you bite off any geolocated data modelling).
If you have the dependencies installed (easy_install sqlalchemy and geoalchemy) and a spatially enabled SQL database running, you can download the script, edit the DB_SETTINGS on line 20 and run using:
python test_geography.py
With that under our belt, let’s look at how we query our Messages. To work out the radius that will yield the desired result volume we can follow this pattern:
* start with a default radius (one we just make up, e.g.: 15km)
* perform a query with that radius as a filter
* evaluate the number of results:
- if we got too many, repeat with a tighter radius
- else if we got too few, repeat with a wider radius
- else we have an adequate result volume =D
This next gist abstracts out the relevant parts of the previous test_geography.py script into a LocationMixin class that can be mixed into any SQLModel class. The get_distance class method on line 113 implements the pattern above using a left-node-right algorithm.
This allows us to write query code that looks like this:
With this code exposed in a request handler, all we need now is a user interface. I’ve collated a few files into a small example app on GitHub here. You can clone the repo, edit the db config as before and bootstrap and then run the example using:
python model.py
python app.py
If you goto localhost:8080 you should see something like this:
As the page has loaded, we’ve initialised a LocationBar widget and an IndexPage view which both share access to a distance object.
When the page loads, the IndexPage view makes a request to /query, with the user’s current geolocation. The request is handled with our query code from before. Because no distance parameter has been provided, the app uses our get_distance method to calculate a filter radius that will return a good volume of results.
When you bootstrapped the app, you generated 500 messages with random locations. If you now play with the location slider, you’ll see the message numbers change as your query now supplies a specific distance parameter. The more you increase the distance, the more recent messages you will get, as more messages are within the filter radius. At lower distances, we start getting all the messages within that radius (down to no messages at all), rather than just the most recent.
If you refresh the page (to get the initial result again) I hope you can see the value of the algorithm in showing you an adequate volume of results that are both recent and nearby. I’d also love to know if this post has proved useful to you or if there are bits that aren’t clear, so do post any comments below.
