Treemapping

Treemapping is a method for displaying tree-structured data using nested rectangles.

Main idea

Treemaps display hierarchical (tree-structured) data as a set of nested rectangles. Each branch of the tree is given a rectangle, which is then tiled with smaller rectangles representing sub-branches. A leaf node's rectangle has an area proportional to a specified dimension on the data. (In the illustration, this is proportional to a waiting time). Often the leaf nodes are colored to show a separate dimension of the data.

When the color and size dimensions are correlated in some way with the tree structure, one can often easily see patterns that would be difficult to spot in other ways. A second advantage of treemaps is that, by construction, they make efficient use of space. As a result, they can legibly display thousands of items on the screen simultaneously.

The tiling algorithm

To create a treemap, one must define a tiling algorithm, that is, a way to divide a rectangle into sub-rectangles of specified areas. Ideally, a treemap algorithm would create rectangles of aspect ratio close to one; would preserve some sense of the ordering of input data; and would change only slowly when the underlying data changes slowly. Unfortunately, these properties have an inverse relationship. As the aspect ratio is optimized, the order of placement becomes less predictable. As the order becomes more stable, the aspect ratio is degraded.

To date, five primary rectangular treemap algorithms have been developed:

*BinaryTree - Partially ordered, high aspect ratios, stable
*Ordered - Partially ordered, medium aspect ratios, medium stability
*Slice And Dice - Ordered, very high aspect ratios, stable
*Squarified - Unordered, lowest aspect ratios, medium stability
*Strip - Ordered, medium aspect ratios, medium stability

In addition, several algorithms have been proposed that use non-rectangular regions:
*Voronoi Treemaps - based on voronoi diagram calculations
*Jigsaw Treemaps - based on the geometry of space-filling curves

History

Area-based visualizations have existed for decades. Mosaic plots and Marimekko diagrams both use rectangular tilings to show joint distributions, for example. The main distinguishing feature of a treemap, however, is the recursive construction that allows it to be extended to hierarchical data with any number of levels. This idea was invented by University of Maryland, College Park professor Ben Shneiderman in the early 1990s. Shneiderman and his collaborators then deepened the idea by introducing a variety of interactive techniques for filtering and adjusting treemaps.

These early treemaps all used the simple "slice-and-dice" tiling algorithm. Despite many desired properties (it is stable, preserves ordering, and is easy to implement) the slice-and-dice method often produces tilings with many long, skinny rectangles. In 1998, Martin Wattenberg and Jarke van Wijk independently invented "squarifying" algorithms that created tilings whose rectangles were closer to square. Using this algorithm, Wattenberg created the first web treemap, the SmartMoney Map of the Market, which displayed data on hundreds of companies in the U.S. stock market. Following its launch, treemaps enjoyed a surge of interest, especially in financial contexts.Fact|date=August 2008

A third wave of treemap innovation came around 2002, after Marcos Weskamp created the "Newsmap", a treemap that displayed news headlines. This example of a non-analytical treemap inspired many imitators, and introduced treemaps to a new, broad audience. In recent years, treemaps have made their way into the mainstream media, including usage by the New York Times.

ee also

* Information visualization
* Panopticode - An open source project that uses Treemaps to visualize software metrics
* Panopticon Software, a commercial provider of Visual business intelligence solutions
* SpaceMonger for Windows
* SequoiaView

External links

Examples

* [http://services.alphaworks.ibm.com/manyeyes/home IBM's Many Eyes] provides web-based treemap tools.
* [http://marumushi.com/apps/newsmap/newsmap.cfm Newsmap] , an example of treemaps applied to news.
* [http://netscan.research.microsoft.com/treemap/ Netscan treemap of Usenet]
* [http://internetmap.juiceanalytics.com/ Map of the Internet] treemap shows major web sites and categories.
* [http://docs.kde.org/kde3/en/kdeaddons/konq-plugins/fsview/index.html FSView] , treemapping plugin for the KDE file manager Konqueror.
* [http://spillett.net/~dirgraph/ dirgraph] directory usage application (Free)
* [http://www.roomformilk.com/ RoomforMilk] A keyword-based news aggregator using Treemaps as primary navigation.
* [http://visudemos.ilog.com/webdemos/treemap/treemap.html ILOG Elixir's Treemap implementation using Flex.]

Academic descriptions

* [http://www.cs.umd.edu/hcil/treemap-history/index.shtml History of Treemaps] by Ben Shneiderman.
* [http://www.cs.umd.edu/hcil/treemap/ Treemap software]
* [http://iv.slis.indiana.edu/sw/treemap.html Indiana University] description
* [http://www.magnaview.nl/documents/Visualizing_Business_Data_with_Generalized_Treemaps.pdf Generalized treemaps]

Open source

* [http://js-treemap.sourceforge.net/ An open-source JavaScript ^treemap
* [http://prefuse.org Prefuse] open source library for visualization that includes treemaps
* [http://code.qnot.org/svn/projects/acts_as_treemap Acts As Treemap] Open source treemap implementation for Ruby on Rails.
* [http://www.codeplex.com/treemaps/ A WPF treemap implementation]
* [http://treemap.sourceforge.net/ An open-source Java treemap]
* [http://jtreemap.sourceforge.net/ JTreeMap, another open-source Java treemap (Swing & SWT)]
* [http://kdirstat.sourceforge.net/ KDirStat] , an open-source treemap
* [http://windirstat.info/ WinDirStat] , an open-source treemap for Microsoft Windows
* [http://treepie.sf.net/ TreePie] , an open-source sunburst diagram (similar to a treemap) for Microsoft Windows
* [http://www.uc.org/read/Treemaps Treemap] , as a Perl module
* [http://gdmap.sourceforge.net/ GdMap] , GTK+ based POSIX application
* [http://docs.kde.org/kde3/en/kdeaddons/konq-plugins/fsview/index.html FSView] (File System View), a KDE/Konqueror plugin
* [http://grandperspectiv.sourceforge.net/ GrandPerspective] , open-source treemap program for Mac OS X
* [http://www.derlien.com/ Disk Inventory X] , open-source treemap program for Mac OS X including a framework

Commercial

* [http://www.panopticon.com Panopticon Software] offers interactive, real-time enabled treemap software as desktop or web software, Java and .NET SDKs.
* [http://www.macrofocus.com/public/products/treemap.html Macrofocus Treemap] An easy to use treemapping tool with some examples (Commercial).
* [http://www.labescape.com/ Lab Escape's Heat Map Explorer] available for the desktop, web or enterprise, or as a treemap SDK.
* [http://www.hivegroup.com/ The Hive Group] develops enterprise treemap software that is used by major corporations and government agencies.
* [http://www.ilog.com/products/jviews/charts ILOG JViews Charts] , a commercial Java library with a [http://svdemo01.ilog.com/jsf-chart-treemap-ws-81/ thin client demo]
* [http://elixir.ilog.com ILOG Elixir] , a commercial Flex library with a [http://visudemos.ilog.com/webdemos/treemap/treemap.html Flex/Flash demo]
* Cross-platform: [http://www.openviz.com/heatmaps.html AVS OpenViz] offers commercial custom made Desktop, Enterprise, and Web enabled Treemap software
* [http://www.heatmaps.co.uk Incito] offer enterprise and desktop Treemap products, that provide easy to use visual analysis tools.
* [http://www.magnaview.nl MagnaView] offers commercial desktop and enterprise visualization products, including a generalized version of treemaps.
* [http://www.jam-software.com/treesize/index.shtml TreeSize] displays used hard disk space as Treemap.
* [http://www.foldersizes.com FolderSizes] provides a hierarchical folder map view, based upon treemap data visualization technique.