1Hierarchies and Trees 2(Space-filling)CS 4460/7450 - Information VisualizationMarch 12, 2009John StaskoSpring 2009 CS 4460/7450Hierarchies• Definition− Data repository in which cases are related to subcases− Can be thought of as imposing an ordering in which cases are parents or ancestors of other cases22Spring 2009 CS 4460/7450Last Time: Node-Link RepsLamping & RaoCard, Mackinlay & RobertsonTraditionalHyperbolic treeConeTreeSpaceTreePlaisant, Grosjean & Bederson3Spring 2009 CS 4460/7450Node-link Shortcoming• Difficult to encode more variables of data cases (nodes)− Shape− Color − Size− …but all quickly clash with basic node-link structure43Spring 2009 CS 4460/7450Space-Filling RepresentationEach item occupies an areaChildren are “contained” under parentOne example5Spring 2009 CS 4460/7450Treemap• Space-filling representation developed by Shneiderman and Johnson, Vis ‘91• Children are drawn inside their parent• Alternate horizontal and vertical slicing at each successive level• Use area to encode other variable of data items64Example3 643751 4235920 6CS 4460/7450Spring 2009 7Example9206CS 4460/74503 643751 4235920 6Spring 2009 85Example9206364375142CS 4460/74503 643751 4235920 6Spring 2009 9Spring 2009 CS 4460/7450Treemap• ExampleDirectories106Spring 2009 CS 4460/7450Treemap ExampleOld one I built for our Sun workstations11Spring 2009 CS 4460/7450Treemap AlgorithmDraw() {Change orientation from parent (horiz/vert)Read all files and directories at this levelMake rectangle for each, scaled to sizeDraw rectangles using appropriate size and colorFor each directoryMake recursive call using its rectangle as focus}127Spring 2009 CS 4460/7450Nested vs. Non-nestedNested Tree-MapNon-nested Tree-Map13Spring 2009 CS 4460/7450Applications• Can use Treemap idea for a variety of domains− File/directory structures− Basketball statistics− Software diagrams− Tennis matches148Spring 2009 CS 4460/7450Software Visualization App• SeeSys: Software Metrics Visualizing System• Uses treemap-like visualization to present different software metrics• Displays:− Size− Recent development− High fix-on-fix rates− History and growthBaker and Eick JVLC ‘9515Spring 2009 CS 4460/7450Sample View 1Subsystems in a software system. Each rectangle represents thenon-comment source code in a subsystem. Area means sizeNew codein this releaseSize169Spring 2009 CS 4460/7450Bug rates by subsystem and directoryRepresentsnew codein this releaseBug fixesAddedfunctionalityBars representindividualdirectories inthe subsystemsSample View 217Spring 2009 CS 4460/7450Tennis Viewing Application• Analyze, review and browse a tennis match• Space-filling/treemap-like hierarchy representation for a competition tree• Shows match,sets,games,points• Uses lenses to show shot patterns• Red/green to encode two players• Composite colors on top of each otherJin and Banks IEEE CG&A ‘971810Spring 2009 CS 4460/7450Visualization Make-upMatchCompositeGamesSet19Spring 2009 CS 4460/7450Simulated Match ResultsMatch viewGame resultsSet resultsBond wonLens showingball movement onindividual points2011Treemap?Spring 2009 CS 4460/7450http://blog.wired.com/wiredscience/2008/06/awesome-infogra.htmlVery nice infographic21Spring 2009 CS 4460/7450Treemap Affordances• Good representation of two attributes beyond node-link: color and area• Not as good at representing structure− What happens if it’s a perfectly balanced tree of items all the same size?− Also can get long-thin aspect ratios− Borders help on smaller trees, but take up too much area on large, deep ones2212Spring 2009 CS 4460/7450Aspect ratiosThese kinds of rectangles are visually unappealingWhich has bigger area?23Spring 2009 CS 4460/7450Variation• Can rectangles be made more square?……think about it……• In general, a very hard problem!2413Spring 2009 CS 4460/7450Variation: “Cluster” Treemap• SmartMoney.com Map of the Market− Illustrates stock movements− “Compromises” treemap algorithm to avoid bad aspect ratios− Basic algorithm (divide and conquer) with some hand tweaking− Takes advantage of shallow hierarchy− www.smartmoney.com/marketmapWattenberg CHI ‘99Image on next slide25Spring 2009 CS 4460/7450 2614Spring 2009 CS 4460/7450Spring 2003 CS 7450 24A goodday :^)27Spring 2009 CS 4460/7450More recent times Sept. 29, 20082815Spring 2009 CS 4460/7450SmartMoney Review• Tufte-esque micro/macro view• Dynamic user interface operations add to impact• One of best applications of an InfoVis techniques that I’ve seen29Spring 2009 CS 4460/7450Other Treemap Variations• Squarified treemap− Bruls, Huizing, van Wijk, EuroGraphics ‘00− Alternate approach, similar results3016Spring 2009 CS 4460/7450Square Algorithm Problems• Small changes in data values can cause dramatic changes in layout• Order of items in a group may be important31Spring 2009 CS 4460/7450New Square Algorithms• Pivot-by-size and pivot-by-middleShneiderman & Wattenberg InfoVis ‘01Partition area into 4 regionsPick pivot element RpSize: Largest elementMiddle: Middle elementR1- elements earlier in list thanpivotR2- elements in list before R3andalso that makes Rp have aspect ratio closest to 13217Spring 2009 CS 4460/7450New Variation• Strip treemapUse strips to place itemsPut new rectangle into stripIf it makes average aspect ratioof all rectangles in strip go down,keep it thereIf it makes aspect ratio go up, putit back and move to next stripBederson, Shneiderman & WattenbergACM Trans on Graphics ‘0233Spring 2009 CS 4460/7450Compare resultswww.cs.umd.edu/hcil/treemap-history/java_algorithms/LayoutApplet.htmlCompare- slice and dice- squarified- strip- pivottechniques by- aspect ratiowidth to height- structural change metric designed tomeasure movements of items- readabilitymetric based on changesin direction of eye gaze as items scanned3418Spring 2009 CS 4460/7450Slice-and-dice ClusterSquarifiedStripPivot-by-sizePivot-by-middle35Spring 2009 CS 4460/7450Showing Structure• Regular borderless treemap makes it challenging to discern structure of hierarchy, particularly large ones− Supplement Treemap view− Change rectangles to other forms3619Spring 2009 CS 4460/7450Variation: Cushion TreemapAdd shading and textureto help convey structureof hierarchyVan Wijk & van de WeteringInfoVis ‘9937Spring 2009 CS 4460/7450SequoiaViewwww.win.tue.nl/sequoiaview/File visualizerbuilt using cushion