Server Side Clustering in C#

Some time ago we launched a new IOS and Android app for trygfonden called "Trygfonden Hjertestart".

It's an app, that gives you information about all defibrillators in denmark. At the moment there is about 6.500 of them, and this number just keep growing every week.

Trygfonden wanted to create a google map with markers for all of these defibrillators/aed's.

This is a strait forward thing to do, if you have less than 1500 markers. But when you have more than 1500 markers, you need to do server side clustering. Otherwise your map would become extremely slow (if you implemented the standard client side clustering, provided by google).

So how does one do server side clustering? When we started this project, i had absolutely no idea about it. My thoughts were, that somebody properly made some cool .net library that we could use or blogged about it...

But in this case google was not my friend :-( Meaning, that i simply could not find any information about it.

So i sad down with a great guy called kunuk and we talked about the problem and after some time we came up with a soulution. I'm sure that there are more complicated ways to do it, and our approach is definetly not perfect world wide.

But it works very well as long as you are on our side of the globe, and it performs very fast with up to 25.000 markers.

So how to we do it?

Well, here's what we did :

1. We cached a complete dataset of all AED's in denmark in memory on the webservers.
2. We created a REST Webservice interface that could return a clustered json response to us. This interface is then called by javascript or the app code, witch then creates the map with all markers on it.

Okay, this seems pretty simple right? But how do we cluster all the markers?

I'll try to give you the basics. And i will also provide you with a code example for you to download.
I will not go into how we do the clustering. It is described with comments in the example code, and it would be a very long entry here, if i should go through everything.

But i will tell you some of the things that you need to know before diving into the code.

What is expected from you?

1. You know how to setup a Rest Webservice. The Interface and methods are provided for you in the code, but the project does not include a website. So you need to know how to set this up, if you want to do clustering from a webservice interface.

2. The example code, does not come with an example dataset. The code provides you with a DataContext class. You will need to know how to modify this to extract all your records from your database, webservice etc.


 What is nessary to do the clustering?

1. First of all, you need to know what the user is looking at. So you need to provide the code with some viewport information (corners of the displayed map).

2. You also need to provide it with the current zoom level and at what zoomlevel you want to stop doing clustering.

3. And last, but not least, you need to provide the Grid Size you want.

What is grid size you might ask? Well, we devide the viewport into a grid and we then cluster all markers within the same grid. So the webservice needs to know how many grids should be created when doing the clustering.

What are the limitations?

1. We only tested this on our side of equator. You will need to modify the code to support the other side of the globe, and it will not support clustering on both sides of the globe at the same time. This could properly be implemented, but we only needed to cluster makers within Denmark, so this is what we decided to support.

2. The soulution has been tested to work with 25.000 markers. It will properly support 100.000 or more, but this has not been tested.

3. The each is round, and this provides a bit of a problem when clustering on big maps. We created a bit of a "hack" for this problem. We simply extented the viewport a bit. Look at the code to see what i mean. This is okay for some soulutions, but might not be the best soulution on very big maps.

There is a Sql soulution for this. Search google for 'Microsoft.SqlServer.Types' and you will find that this DLL file has some methods to tell you if a point is within a viewport.

This soulution is much more precise, but it is also much slower. We implemented it at first, but quickly found that it took way to long to filter data ourside the viewport (around 2 seconds for 6.500 markers). And as we needed this to be very fast, we went with our own "hack" soulution, witch works great in the real world, as long as your viewport is not bigger than 1000 km or so.


If you have any questions regarding the code, please feel free to comment. Also it's always nice to know if you found this post usefull.

Where can i see it in action?

You can download the Hjertestart IOS app or you can go to http://www.hjertestarter.dk/Kort

If you go to the website using FireFox, and you have Firebug installed. You can see how the Webservice is called and what the response times are. Depending on the amount of clusteres returned and where you are located in the woruld (ping issues), the response times should be between 100 and 300 ms.


Download the Example code from here

Best Regards.
Lasse Rasch