locked
Clustering vs Tile Layers RRS feed

  • Question

  • My colleagues and I are in the exploratory phase of designing a spatial app using Bing Maps and Silverlight 4.  We know we will have to handle extremely large data sets so our goal is to be able to represent up to a 1,000,000 points on the screen in some way, shape or form.  This could happen if our users zoom out to view the entire USA and what to see where their points are located.

    I have experimented with MapTileLayers that use a custom web service which draws the points on a transparent PNG to lay over the base map.  Once drawn, the tiles are then stored in the DB for future use.  This works pretty well.  The initial drawing of the tiles can be a rather expensive operation in particularly dense areas of the map, however once the tile is drawn retrieving that tile from the DB is pretty snappy.

    Now I'm trying to figure out how to handle modifications to a point; the most common change in our app will be the shape and/or color of the pushpin.  Since redrawing a tile that represents 100,000 points just because 1 changed color seems ludicrous, I'm starting to explore clustering.

    Does anyone have any wisdom they could share regarding the advantages/disadvantages of clustering (either client- or server-side)?


    • Edited by rsaltrelli Monday, October 24, 2011 6:52 PM
    • Edited by Ricky_Brundritt Saturday, March 10, 2012 11:44 AM
    • Changed type Ricky_Brundritt Saturday, March 10, 2012 11:45 AM
    • Moved by Ricky_Brundritt Saturday, March 10, 2012 11:46 AM (From:Bing Maps: Map Control and Web services Development)
    Monday, October 24, 2011 6:43 PM

Answers

  • Take a look at this simple optimization for Map Layers: http://rbrundritt.wordpress.com/2010/11/19/optimize-map-layers-in-bing-maps-silverlight/ This works great for pushpins. You could also consider pre clustering the data when the map initially loads. Simple calculate the clusters for all zoom levels and store the clustered information for the higher zoom levels.
    http://rbrundritt.wordpress.com
    Tuesday, October 25, 2011 8:28 AM
  • If the data doesn´t change that often i.e. maybe once a day. Then you can `recluster your data on the server side. yu could then store the clusters in either a DB or in memory. I´ve since a great solution that store all the data in memory and this made for wicked fast clustering of 1 miliion+ locations.
    http://rbrundritt.wordpress.com
    Friday, October 28, 2011 6:18 PM

All replies

  • i can't say whether to choose clustering or tile layer but if you decided to take clustering here are some algorithms:

     

    DBSCAN (good results, not the fastest. Look at the comments for QT and Fixed-With Method): http://www.c-sharpcorner.com/UploadFile/b942f9/6174/

     

    K-Means (mulithreaded): http://www.codethinked.com/multi-threaded-k-means-clustering-in-net-40

     

    good luck!

    Tuesday, October 25, 2011 7:04 AM
  • Take a look at this simple optimization for Map Layers: http://rbrundritt.wordpress.com/2010/11/19/optimize-map-layers-in-bing-maps-silverlight/ This works great for pushpins. You could also consider pre clustering the data when the map initially loads. Simple calculate the clusters for all zoom levels and store the clustered information for the higher zoom levels.
    http://rbrundritt.wordpress.com
    Tuesday, October 25, 2011 8:28 AM
  • After playing around with clustering for a few days, I found that for large data sets it is not practical to REPLACE tile layers with clustering.  It is just as expensive to gather all of the individual points and cluster them (even server-side) as it is to draw them all on a tile plus the cluster cannot be saved and reused later like a tile.  I did find, however,  that clustering IS appropriate upon switching from raster to vector representations.  My prototype app switches to a vector representation at zoom level 12, but even at this point there can be a few thousand points on the screen.  Clustering has greatly helps with map responsiveness.  And as the user zooms in further, the larger clusters dissolve into smaller cluster and ultimately into individual points.  Very cool!
    Friday, October 28, 2011 5:23 PM
  • If the data doesn´t change that often i.e. maybe once a day. Then you can `recluster your data on the server side. yu could then store the clusters in either a DB or in memory. I´ve since a great solution that store all the data in memory and this made for wicked fast clustering of 1 miliion+ locations.
    http://rbrundritt.wordpress.com
    Friday, October 28, 2011 6:18 PM
  • So to do this you'd have to make multiple versions of each cluster (1 per applicable zoom level) and tag it with a QuadKey, correct? I suppose that's pretty much what I'm doing with my tiles. So it boils down to personal preference then.  Do you prefer to see clusters or tiles on the map? Interesting.
    Friday, October 28, 2011 6:25 PM