Tracing its ancestry to Venn diagrams (Venn,1971), the Treemap algorithm was developed in the HCI Lab at the University of Maryland. It uses a space filling technique to map a tree structure (e.g. file directory) into nested rectangles with each rectangle representing a node. A rectangular area is first allocated to hold the representation of the tree, and this area is then subdivided into a set of rectangles that represent the top level of the tree. This process continues recursively on the resulting rectangles to represent each lower level of the tree, each level alternating between vertical and horizontal subdivision.
The parent-child relationship is indicated by enclosing the child-rectangle by its parent-rectangle. That is, all descendents of a node are displayed as rectangles inside its rectangle. Associated with each node is a numeric value (e.g. size of a directory) and the size of a nodes rectangle is proportional to its value. Ben Shneiderman's 'Treemaps for space-constrained visualization of hierarchies' webpage provides the full story. Many efforts have been made to make the space filling technique more effective in visualizing information hierarchy:
"Treemaps are a family of algorithms that are space-filling partitions of a two-dimensional area. Treemaps take as input a list of n numbers and a rectangle. They partition the area into nrectangles, one per input number. The rectangles are guaranteed to fill the input rectangle, and the rectangles are proportional in area to the list of input numbers. Treemaps are designed to be applied hierarchically, so any given resulting rectangle can itself contain a treemap, and so on, recursively." - 'Treemaps for space-constrained visualization of hierarchies'
"The goal of the Quantum Treemap algorithm is similar to other treemap algorithms, but instead of generating rectangles of arbitrary aspect ratios, it generates rectangles with widths and heights that are integer multiples of a given elemental size. In this manner, it always generates rectangles in which a grid of elements of the same size can be layed out. Furthermore, all the grids of elements will align perfectly with rows and columns of elements running across the entire series of rectangles. It is this basic element size that cannot be made any smaller that led to the name of Quantum Treemaps." - 'Treemaps for space-constrained visualization of hierarchies'
"Bubblemap is a new algorithm which lays out groups of quantum-sized objects in an ordered position with no wasted space per group, although there is a small amount of wasted space for the entire area. The groups of objects can be created in different shapes, such as rectangular or circular, but the groups of objects only approximate those shapes, rather than define them exactly. The Bubblemap algorithm has also been integrated into PhotoMesa as a user-selectable layout option." - 'Treemaps for space-constrained visualization of hierarchies'
Brian Johnson & Ben Shneiderman in their widely cited paper (1991) consider the algorithm "best suited to hierarchies in which the content of the leaf nodes and the structure of the hierarchy are of primary importance, and the content information associated with internal nodes is largely derived from their children."
Treemaps make 100% use of the available display space and efficiently display large trees in limited space. All the leave nodes can be viewed. Area-size and color coded attributes of a node can be recognized very easily.
Treemaps should not be used if the hierarchical structure of a LARGE data set needs to be conveyed.
SmartMoney Stock Market visualization shows 535 popularly held stocks that are organized by industry groups, size-coded by market capitalization, and color-coded to show rise or fall: http://www.smartmoney.com/marketmap/http://www.truepeers.com/
TruePeers People Maps http://www.truepeers.com/
Marc Smith (http://research.microsoft.com/~masmith/) applies treemaps to visualize the structure of newsgroups.
Smithsonian Institution's HistoryWired web site introduces visitors to some of the three million objects held by the National Museum of American History, Behring Center using a interactive treemap designed by SmartMoney. http://historywired.si.edu/index.html
In class, we will use the treemap implementations in the Information Visualization XML Toolkit.
Treemap from HCIL, University of Maryland is available at http://www.cs.umd.edu/hcil/treemap/index.shtml XDU is a program for displaying a graphical tree of disk space utilization as reported by the UNIX utility "du". You can navigate up and down in the tree, sort things, and print out information.
Read Visualizing Tree Data to learn how to run and use the existing code.
The code was taken from www.bouthier.net. Nathan James Deckard integrated the code into the XML Toolkit.