Tuesday, February 8, 2011

Clustering is key to map application success

In view of rising smartphone demand, new Location Based Services (LBS) are being introduced almost on a daily basis. If you share your position with these services, they will connect you with friends or recommend businesses that are physically located nearby. In most cases LBS are all about social geolocation and navigation.

A map view is the natural way to visualize the matching POIs (points of interest) around you. Now imagine looking at the restaurants in your town from a distance (e.g. from an aeroplane): Depending on the zoom level and service, an app can easily deliver hundreds or even thousands of POIs.

And, unfortunately, lots of applications really do ... they clutter the map with hundreds or thousands of markers. In this scenario, markers overlap. Users run into problems trying to select the POI they want on the map and end up accidentally selecting the wrong one.

Other apps artificially limit the number of results and ask users to either narrow their search or zoom in further until results are within a range that displays well. This sounds decent in theory but, in reality, is confusing and frustrating to analytical users.

Both approaches limit usability without a reason. Even when there are dynamic components (like yourself driving in a car) involved, the mayority of POIs like shops etc. are static: You are moving, not the bricks and mortars.

The solution is very simple: Just combine overlapping static markers until you get close enough to see the details. This concept is called clustering. So from the plane we would only see some restaurant clusters distributed within the city limits, but when we get closer e.g. on a quarter or street level we see single markers for each and every restaurant located nearby. Data represenation feels smooth and clean while the user always receives the perfect information level: An overview from the distance and the full details from the next-door location.

So if clustering is key for any map based application - why don't we see more clustering in the wild?

The reason is trivial: Developing clustering solutions is not trivial. It's actually quite a challenging task.

Client-side solutions don't make much sense; a browser would need to receive all the marker data and do some heavy clustering calculations, just to finally render a minimal subset of the original coordinates on the map. Note well, this expensive computation needs to be done every time search parameters are redefined.

So clustering must happen on the server-side. Some RDBMS do support GIS data but lack flexibility, extensibility, and often performance.

Clustering on casa.keru is provided by the Tredix Internet Find Store (IFS). The framework stores all POI data and offers comprehensive search support for map based applications.

In the clustering scenario, casa.keru simply requests the POIs for a given map dimension via HTTP GET and receives a standard JSON response containing the perfect cluster and marker selection - done! No, it's not even necessary to specify a zoom level. And yes, it works cross-domain.

IFS services are highly customizable. In the case of casa.keru, besides geometric clustering there was a need for editorial clustering. We provided the IFS with fixed cluster points marking the centers of districts, counties, and parishes. These should dynamically mix with geometric clusters or under certain conditions even merge with them - no problem.

Clustering is just one out of many forward-looking IFS search service features that made their way into casa.keru.pt, providing the website with a significant competitive advantage. We'll follow up on other key services of the framework on this blog, so stay tuned.

IFS services can be rented from Tredix GmbH.

1 comment: