Client Side Point Based Clustering

Several years ago I wrote an algorithm for Bing Maps that used grid based clustering. Grid base clustering is where you break the map into a grid and if any two pushpins are in the same grid cell they are clustered together. Over time this algorithm saw a lot of use and eventually became a built in part of the Bing Maps V6.3 API. Earlier this year I created a version of this algorithm for Bing Maps V7 and it soon became the first module for this API. As great as this algorithm has been there has always been two downfalls. The first being that clustered pushpins would occasionally overlap when using the mean average positioning method for the cluster. The second issue being that every time you moved the map the data would re-cluster. This was by design as it meant that only the data in view needed to be broken up into clusters. This allows this algorithm to cluster 5000+ pushpins.

Point based clustering is something I’ve had in the back of my mind for the past few years but always seemed to run into performance issues which made the algorithm useless. Recently the idea popped back into my head and I started thinking about how I could over come the performance issues. I ended up coming up with two ways to reduce the performance issues, the first being indexing of the data, and the second method was to separate the clustering logic from the rendering logic. By adding indexing I was able to store the cluster information for each zoom level. This meant that the algorithm didn’t need to re-cluster when it got to a zoom level it has already been to. The rendering logic gets fired as map is moved so that only the data that’s in view is rendered. By doing this I managed to get decent performance as can be seen in the below chart.

That said this algorithm appears to perform at expectable levels with 2000 or less pushpins. This isn’t as good as the Grid Base Clustering but much better than what I’ve experienced in the past. The Grid Base Clustering algorithm is much faster but doesn’t have as good of a user experience as the Point Based Clustering algorithm. The grid based algorithm is recommended if you need to cluster more than 2000 pushpins in JavaScript. Tests have found that this algorithm can easily handle 5000+ pushpins.

You can download both these algorithms with sample code from the Bing Maps V7 Modules CodePlex project.