Posts Tagged ‘clustering’

MarkerClusterer in an All New Flavor – ActionScript! (GoogleGeoDev)

Friday, August 14th, 2009

[Editor's note: An AS3 Flash / Flex library for auto-clustering near map location markers into groups symbols. This speeds map rendering and groups points all within the same neighborhood, avoiding "red dot fever" marker overload. An AS3 implementation of existing JavaScript extension. Still needs to account for geographic region clustering (not just within a grid). Thanks Laris!]

Republished from Google Geo Developer Blog.
Monday, July 27, 200. 

My name is XIAO Juguang – just call me Juguang. I am a freelance software developer based in Beijing, China. Technically speaking, I’m double sided. On one side, I specialize in knowledge management and business modeling, traditionally using LAMP and now experimenting with offerings like Google App Engine. On the other side, I love visualization in time and space, with charts, trees, graphs, and maps, always using the power of ActionScript/Flex, with the help of open-source projects like Degrafa, Axiis, and Birdeye, and of course, APIs like the Google Maps API for Flash.

A few month ago, Xiaoxi Wu (also from China!) created the MarkerClusterer library for the Google Maps JavaScript API v2 and released it in their open source utility library. This library did automatic clustering of markers placed on a map, so that a large amount of markers wouldn’t overcrowd the map or overwhelm the user. This is a great technique for having a better performing map (see this talk for more tips on improving map performance), and the Flash map community immediately rushed to port the code to ActionScript. Developer Sean Toru posted the first port, a version that was only Flash-compatible, Ian Watkins modified that port to use Flex packages, and then I refactored the code to be more ActionScript-friendly and released it into the open-source library. It’s great when random strangers can collaborate together on a common code goal. :)

To see how the AS3 MarkerClusterer works, try out the demo (shown above). As you zoom and pan the map, you can witness how the markers are clustered and re-clustered. To learn how to use MarkerClusterer on your own map, view the source code of the demo. To use the library, check out the source code and import it into your project.

The current algorithm is quite simple, just clustering markers in a grid and using static images for the cluster markers. Future extensions could include support for regional clustering or using arbitrary DisplayObjects for the cluster markers. If you’re interested in extending the library, join the project.

Travellr: Behind the Scenes of our Region-Based Clusters (Google GeoDev)

Monday, July 6th, 2009

[Editor's note: The age-old rule for cloropleth mapping that suggests aggregation by multi-scale areal units based on the map's zoom level is slowly seeping into "clustering" for the point-based mashup geo community. This overview from Travellr published on the Google GeoDevelopers blog includes two illustrations that show the power of this technique. I used such a technique (different implementation) on The Washington Post's recent swine flu mapping.]

Republished from Google GeoDevelopers Blog.
Monday, June 22, 2009

Recently, there has been a lot of interest in clustering algorithms. The client-side grid-based MarkerClusterer was released in the open source library this year, and various server-side algorithms were discussed in the Performance Tips I/O talk. We’ve invited the Travellr development team to give us insight on their unique regional clustering technique.

Travellr is a location aware answers service where people can ask travel-related questions about anywhere in the world. One of its features is a map-based interface to questions on the site using Google Maps.

dxjmnbf_4t5qkqpfw_b1
Figure 1. An example of the Travellr Map, showing question markers for Australia.

Clustering for usability
We learned that the best way to display markers without cluttering our map was to cluster our questions depending on how far you zoom in. If the user was looking at a map of the continents, we would cluster our questions into a marker for each continent. If the user zoomed-in to France we would then cluster our questions into a marker for each region or city that had questions. By clustering our data into cities, regions/states, countries, and continents, we could display relevant markers on the map depending on what zoom level the user was looking at.

Optimizing for Clustering
Our next challenge was how to extract clustered data from our database without causing excessive server load. Every time the user pans and zooms on the map, we need to query and fetch new clustered data in order to display the markers on the map. We also might have to limit the data if the user has selected a tag, as we’re only interested in a questions related to a topic (ie: “surfing”). To execute this in real-time would be painstakingly slow, as you would need to to cluster thousands of questions in thousands of locations with hundreds of tags on the fly. The answer? Pre-cluster your data of course!

Step 1. Structure your location data
When a question is asked about a city on Travellr, we also know its region/state, country and continent. We store more than 55,000 location points as a hierarchy, with each location “owning” its descendent nodes (and all of their data). Our locations are stored in a Modified Preorder Tree (also called Nested Sets). Modified Preorder Trees are a popular method of storing hierarchical data in a flat database table, having a focus on efficient data retrieval, and easy handling of sub trees. For each location we also keep a record of its depth within the tree, its location type (continent, country, region/state, or city), and its co-ordinates (retrieved using the Google Maps geocoder).

Step 2. Aggregate your data
We calculate aggregate data for every branch of our locations tree ahead of time. By storing aggregate data for cities, regions/states, countries, and continents, we provide an extremely fast and inexpensive method to query our locations database for any information regarding questions asked about a particular location. This data is updated every few minutes by a server-side task.

Our aggregations include:

  • Total question count for a location
  • Most popular tags for that location
  • Number of questions associated with each of those tags.

How we query our structured, aggregate data on the map
Whenever the user zooms or pans the map we fire off a query to our (unpublished ;) API with the tags they are searching for, the current zoom level, and the edge co-ordinates of the map’s bounding box. Based on the zoom level (Figure 2) we work out whether we want to display markers for continents, countries, states, or cities. We then send back the data for these markers and display them on the map.

dc287ncr_29cb84v7ct_b
Figure 2. Clustering at different zoom levels (blue = continents, countries, pink = states, cities)

Everyone Wins
So what is the result of structuring and aggregating our data in such a way? It means that we have nicely organized, pre-clustered data that can be read from cheaply and easily. This allows us to provide a super-fast map interface for Travellr that puts minimal load on our infrastructure. Everyone is happy!

Comments or Questions?
We’d love to hear from you if you have any questions on how we did things, or suggestions or comments about Travellr’s map. This article was written by Travellr’s performance and scalability expert Michael Shaw (from Insight4) and our client-side scripting aficionado Jaidev Soin.

You can visit Travellr at www.travellr.com, or follow us on Twitter at twitter.com/travellr.

Flow Mapping (Box Shaped World)

Tuesday, June 2nd, 2009

uk-interdependenceminard

[Editor's note: Flow maps have always ranked high on my radar but constructing them has always been tedious. This post and academic paper link detail how they can be automated with programatically, including edge routing (not directly from A to B, but with bends to not overlap other connections).]

Republished from Box Shaped World.

Getting a head start on a new project that is more cartographic. It will involve mapping migration/flows from Australia to the Northern Territory (probably smaller geographic units than states). I like making maps, and so I’m excited to do some cartography beyond standard ArcGIS layouts. There are different possibilities on how to map this. Initially, I think I will use something like this that creates a more trunk/branch flow map instead of the typical straight line between places (Tobler’s Flowmapper). The project lead doesn’t like this style too much, but thought the trunk/branch style might work. We might pursue other mapping techniques, which would be cool to try and apply different map techniques to this area…

Continue reading at Box Shaped World . . .

Republished from Stanford Graphics paper.

Cartographers have long used flow maps to show the movement of objects from one location to another, such as the number of people in a migration, the amount of goods being traded, or the number of packets in a network. The advantage of flow maps is that they reduce visual clutter by merging edges. Most flow maps are drawn by hand and there are few computer algorithms available. We present a method for generating flow maps using hierarchical clustering given a set of nodes, positions, and flow data between the nodes. Our techniques are inspired by graph layout algorithms that minimize edge crossings and distort node positions while maintaining their relative position to one another. We demonstrate our technique by producing flow maps for network traffic, census data, and trade data.

Continue reading past abstract, includes source code . . .

New Feature: Cluster Your Map’s Markers (Click2Map)

Monday, November 3rd, 2008

[Editor's note: I learned about this technology from Click2Map for selecting markers in Google maps using a building tool and grouping them together as 1 marker at certain zoom levels. I'm not sure it is the best solution... but I like that the functionality is there. Seems like there should also be a more general solution for auto aggregation and disaggregation based on zoom level. I have seen this at a few sites, including Every Block. There is a tip on this a the ESRI mapping center for more GIS focused folks.]

All content below from Click2Map press release . . .

The team of Click2Map is proud to officially launch a feature that tackles one of the major weaknesses of online maps: Crowded maps.

The experience of maps is often diminished when markers are concentrated in a specific location, therefore lapping over one another. Here at Click2Map, as some of you already know, we are dedicated to take Google Maps to a higher level of control for your various professional needs.

Hence the auto-cluster feature! The auto-cluster feature is an easy-to-use tool of our map editor that will enable you to create a unique marker for each area where markers are too densely concentrated. Visitors can simply click on this unique marker to unveil the list of markers it withholds.

Movie Stars in Hollywood
View full page map

The clustering tool enables you to laser-tune the display of your clustered markers based on 3 parameters:
- Clustering rate: the higher the rate, the more markers will be cluttered
- Minimum markers: indicates the number of markers necessary to start building a cluster
- Maximum zoom: indicates from which level of zoom markers won’t be clustered anymore

The video below shows the new auto-clustering tool in action for the Hollywood celebrities’ map we created for the occasion.

To conclude, here is why the auto-clustering tool is a big deal for us:
1. It tackles the problem of markers overlap.
2. It becomes a new productivity tool for power-mapbuilders looking for the perfect map design.
3. It is so easy to apply that even first-time mapbuilders can figure it out on the fly.

Visit Click2Map