Treemapping
In
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 of the data.[1] 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, such as whether a certain color is particularly relevant. 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.
Tiling algorithms
To create a treemap, one must define a tiling algorithm, that is, a way to divide a region into sub-regions of specified areas. Ideally, a treemap algorithm would create regions that satisfy the following criteria:
- A small aspect ratio—ideally close to one. Regions with a small aspect ratio (i.e., fat objects) are easier to perceive.[2]
- Preserve some sense of the ordering in the input data (ordered).
- Change to reflect changes in the underlying data (high stability).
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.[
Rectangular treemaps
To date, fifteen primary rectangular treemap algorithms have been developed:
Algorithm | Order | Aspect ratios | Stability |
---|---|---|---|
BinaryTree | partially ordered | high | stable |
Slice And Dice[4] | ordered | very high | stable |
Strip[5] | ordered | medium | medium stability |
Pivot by middle[6] | ordered | medium | medium stability |
Pivot by split[6] | ordered | medium | low stability |
Pivot by size[6] | ordered | medium | medium stability |
Split[7] | ordered | medium | medium stability |
Spiral[8] | ordered | medium | medium stability |
Hilbert[9] | ordered | medium | medium stability |
Moore[9] | ordered | medium | medium stability |
Squarified[10] | ordered | low | low stability |
Mixed Treemaps[11] | unordered | low | medium stability |
Approximation[12] | unordered | low | medium stability |
Git[13] | unordered | medium | stable |
Local moves[14] | unordered | medium | stable |
Convex treemaps
Rectangular treemaps have the disadvantage that their aspect ratio might be arbitrarily high in the worst case. As a simple example, if the tree root has only two children, one with weight and one with weight , then the aspect ratio of the smaller child will be , which can be arbitrarily high. To cope with this problem, several algorithms have been proposed that use regions that are general convex polygons, not necessarily rectangular.
Convex treemaps were developed in several steps, each step improved the upper bound on the aspect ratio. The bounds are given as a function of - the total number of nodes in the tree, and - the total depth of the tree.
- Onak and Sidiropoulos[15] proved an upper bound of .
- De-Berg and Onak and Sidiropoulos[16] improve the upper bound to , and prove a lower bound of .
- De-Berg and Speckmann and van-der-Weele[17] improve the upper bound to , matching the theoretical lower bound. (For the special case where the depth is 1, they present an algorithm that uses only four classes of 45-degree-polygons (rectangles, right-angled triangles, right-angled trapezoids and 45-degree pentagons), and guarantees an aspect ratio of at most 34/7.)
The latter two algorithms operate in two steps (greatly simplified for clarity):
- The original tree is converted to a binary tree: each node with more than two children is replaced by a sub-tree in which each node has exactly two children.
- Each region representing a node (starting from the root) is divided to two, using a line that keeps the angles between edges as large as possible. It is possible to prove that, if all edges of a convex polygon are separated by an angle of at least , then its aspect ratio is . It is possible to ensure that, in a tree of depth , the angle is divided by a factor of at most , hence the aspect ratio guarantee.
Orthoconvex treemaps
In convex treemaps, the aspect ratio cannot be constant - it grows with the depth of the tree.
To attain a constant aspect-ratio, Orthoconvex treemaps
For the special case where the depth is 1, they present an algorithm that uses only rectangles and L-shapes, and the aspect ratio is at most ; the internal nodes use only rectangles with aspect ratio at most .
Other treemaps
- Voronoi Treemaps
- [18] based on Voronoi diagram calculations. The algorithm is iterative and does not give any upper bound on the aspect ratio.
- Jigsaw Treemaps[19]
- based on the geometry of space-filling curves. They assume that the weights are integers and that their sum is a square number. The regions of the map are rectilinear polygons and highly non-ortho-convex. Their aspect ratio is guaranteed to be at most 4.
- GosperMaps
- [20] based on the geometry of Gosper curves. It is ordered and stable, but has a very high aspect ratio.
History
Area-based visualizations have existed for decades. For example,
These early treemaps all used the simple "slice-and-dice" tiling algorithm. Despite many desirable 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 1994 Mountaz Hascoet and
A third wave of treemap innovation came around 2004, 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.[citation needed] In recent years, treemaps have made their way into the mainstream media, including usage by the New York Times.[23][24]
The Treemap Art Project
See also
- Disk space analyzer
- Data and information visualization
- List of countries by economic complexity, which includes a list of Products Exports Treemaps.
- Marimekko Chart, a similar concept with one level of explicit hierarchy.
References
- .
- S2CID 11597084.
- S2CID 189898065.
- ^ Shneiderman, Ben (2001). "Ordered treemap layouts" (PDF). Infovis: 73.
- S2CID 7253456.
- ^ a b c Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
- ^ Engdahl, Björn. Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies.
- (PDF) from the original on Aug 8, 2022.
- ^ S2CID 6099935.
- ^ Bruls, Mark; Huizing, Kees; van Wijk, Jarke J. (2000). "Squarified treemaps". In de Leeuw, W.; van Liere, R. (eds.). Data Visualization 2000: Proc. Joint Eurographics and IEEE TCVG Symp. on Visualization (PDF). Springer-Verlag. pp. 33–42..
- ^ Roel Vliegen; Erik-Jan van der Linden; Jarke J. van Wijk. "Visualizing Business Data with Generalized Treemaps" (PDF). Archived from the original (PDF) on July 24, 2011. Retrieved February 24, 2010.
- .
- ^ Vernier, E.; Comba, J.; Telea, A. (2018). "Quantitative comparison of dy-namic treemaps for software evolution visualization". Conferenceon Software Visualization: 99–106.
- S2CID 27739774.
- ^ Krzysztof Onak; Anastasios Sidiropoulos. "Circular Partitions with Applications to Visualization and Embeddings". Retrieved June 26, 2011.
- arXiv:1009.1866.
- ^ S2CID 12973376.. Conference version: Convex Treemaps with Bounded Aspect Ratio(PDF). EuroCG. 2011.
- ^ Balzer, Michael; Deussen, Oliver (2005). "Voronoi Treemaps". In Stasko, John T.; Ward, Matthew O. (eds.). IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA (PDF). IEEE Computer Society. p. 7..
- ^ Wattenberg, Martin (2005). "A Note on Space-Filling Visualizations and Space-Filling Curves". In Stasko, John T.; Ward, Matthew O. (eds.). IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA (PDF). IEEE Computer Society. p. 24..
- S2CID 15050386..
- S2CID 1369287.
- ^ Ben Shneiderman; Catherine Plaisant (June 25, 2009). "Treemaps for space-constrained visualization of hierarchies ~ Including the History of Treemap Research at the University of Maryland". Retrieved February 23, 2010.
- ^ Cox, Amanda; Fairfield, Hannah (February 25, 2007). "The health of the car, van, SUV, and truck market". The New York Times. Retrieved March 12, 2010.
- ^ Carter, Shan; Cox, Amanda (February 14, 2011). "Obama's 2012 Budget Proposal: How $3.7 Trillion is Spent". The New York Times. Retrieved February 15, 2011.
- ^ "Treemap Art". Archived from the original on Dec 5, 2023.
- ^ "Every AlgoRiThm has ART in it: Treemap Art Project". CPNAS. Archived from the original on Oct 8, 2023.
External links
- Treemap Art Project produced exhibit for the National Academies in Washington, DC
- "Discovering Business Intelligence Using Treemap Visualizations", Ben Shneiderman, April 11, 2006
- Comprehensive survey and bibliography of Tree Visualization techniques
- Vliegen, Roel; van Wijk, Jarke J.; van der Linden, Erik-Jan (September–October 2006). "Visualizing Business Data with Generalized Treemaps" (PDF). IEEE Transactions on Visualization and Computer Graphics. 12 (5): 789–796. S2CID 18891326. Archived from the original(PDF) on 24 July 2011.
- History of Treemaps by Ben Shneiderman.
- Hypermedia exploration with interactive dynamic maps Paper by Zizi and Beaudouin-Lafon introducing the squarified treemap layout algorithm (named "improved treemap layout" at the time).
- Indiana University description
- Live interactive treemap based on crowd-sourced discounted deals from Flytail Group
- Treemap sample in English from The Hive Group
- Several treemap examples made with Macrofocus TreeMap
- Visualizations using dynamic treemaps and online treemapping software by drasticdata