Loading AI tools
Visualisation method for hierchical data From Wikipedia, the free encyclopedia
In information visualization and computing, treemapping is a method for displaying hierarchical data using nested figures, usually rectangles.
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.
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:
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.[example needed]
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 |
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.
The latter two algorithms operate in two steps (greatly simplified for clarity):
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[17] can be used. There, all regions are orthoconvex rectilinear polygons with aspect ratio at most 64; and the leaves are either rectangles with aspect ratio at most 8, or L-shapes or S-shapes with aspect ratio at most 32.
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 .
Area-based visualizations have existed for decades. For example, mosaic plots (also known as Marimekko diagrams) use rectangular tilings to show joint distributions (i.e., most commonly they are essentially stacked column plots where the columns are of different widths). 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 professor Ben Shneiderman at the University of Maryland Human – Computer Interaction Lab in the early 1990s. [21][22] 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 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 Michel Beaudouin-Lafon invented a "squarifying" algorithm, later popularized by Jarke van Wijk, that created tilings whose rectangles were closer to square. In 1999 Martin Wattenberg used a variation of the "squarifying" algorithm that he called "pivot and slice" to create the first Web-based 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.[citation needed]
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[25] produced 12 framed images for the National Academies (United States), shown the Every AlgoRiThm has ART in It exhibit[26] in Washington, DC and another set for the collection of Museum of Modern Art in New York.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.