1 Hierarchies and Trees 1 (Node-link) CS 7450 - Information Visualization October 28, 2013 John Stasko Topic Notes Fall 2013 CS 7450 Hierarchies • 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 cases 22 Fall 2013 CS 7450 Hierarchies in the World • Pervasive  Family histories, ancestries  File/directory systems on computers  Organization charts  Animal kingdom: Phylum,…, genus,…  Object-oriented software classes  ... 3 Fall 2013 CS 7450 Trees • Hierarchies often represented as trees  Directed, acyclic graph • Two main representation schemes  Node-link (today)  Space-filling 43 Fall 2013 CS 7450 Node-Link Diagrams • Root at top, leaves at bottom is very common 5 Fall 2013 CS 7450 Sample Representation From: Johnson & Shneiderman, ‘91 64 Election ‘12 Fall 2013 CS 7450 7 http://elections.nytimes.com/2012/results/president/scenarios Fall 2013 CS 7450 Examples Good for? Bad for? Search Understanding structure 85 Fall 2013 CS 7450 Why Put Root at Top? Root can be at center with levels growing outward too Can any node be the root? 9 Basic Algorithm Fall 2013 CS 7450 10 • Recursive algorithm • Height on separate levels • Width in unique columns • Make room for subtrees upwards6 Fall 2013 CS 7450 Potential Problems • For top-down, width of fan-out uses up horizontal real estate very quickly  At level n, there are 2n nodes • Tree might grow a lot along one particular branch  Hard to draw it well in view without knowing how it will branch 11 Fall 2013 CS 7450 More Sophisticated In what way? • Regions compressed horizontally 127 Reingold-Tilford Algorithm Fall 2013 CS 7450 13 Compact layout Uses symmetry Depth on levels Generalized from binary trees by Walker Running time improved (linear) by Buchheim et al Neat Applet Fall 2013 CS 7450 14 http://www.cfm.brown.edu/people/hu/cs252/online.html You do drawing It cleans it up8 Fall 2013 CS 7450 InfoVis Solutions • Techniques developed in Information Visualization largely try to assist the problems identified in the last slide • Alternatively, Information Visualization techniques attempt to show more attributes of data cases in hierarchy or focus on particular applications of trees 15 Fall 2013 CS 7450 SpaceTree • Uses conventional 2D layout techniques with some clever additions Grosjean, Plaisant, Bederson InfoVis ‘02 Video & Demo 169 Fall 2013 CS 7450 Characteristics • Vertical or horizontal • Subtrees are triangles  Size indicates depth  Shading indicates number of nodes inside • Navigate by clicking on nodes  Strongly restrict zooming 17 Fall 2013 CS 7450 Design Features • Make labels readable • Maximize number of levels opened • Decompose tree animation • Use landmarks • Use overview and dynamic filtering 1810 Fall 2013 CS 7450 3D Approaches • Add a third dimension into which layout can go • Compromise of top-down and centered techniques mentioned earlier • Children of a node are laid out in a cylinder “below” the parent  Siblings live in one of the 2D planes 19 Fall 2013 CS 7450 Cone Trees Video Developed at Xerox PARC 3D views of hierarchies such as file systems Robertson, Mackinlay, Card CHI ‘91 2011 Fall 2013 CS 7450 Alternate Views 21 Fall 2013 CS 7450 Cone Trees • Pros & Cons?  Discuss 2212 Fall 2013 CS 7450 Cone Trees • Pros  More effective area to lay out tree  Use of smooth animation to help person track updates  Aesthetically pleasing • Cons  As in all 3D, occlusion obscures some nodes  Non-trivial to implement and requires some graphics horsepower 23 Fall 2013 CS 7450 Alternative Solutions • Change the geometry • Apply a hyperbolic transformation to the space • Root is at center, subordinates around • Apply idea recursively, distance decreases between parent and child as you move farther from center, children go in wedge rather than circle 2413 Fall 2013 CS 7450 Hyperbolic Browser • Focus + Context Technique  Detailed view blended with a global view • First lay out the hierarchy on the hyperbolic plane • Then map this plane to a disk • Start with the tree’s root at the center • Use animation to navigate along this representation of the plane Lamping and Rao, JVLC ‘96 25 Fall 2013 CS 7450 2D Hyperbolic Browser • Approach: Lay out the hierarchy on the hyperbolic plane and map this plane onto a display region. • Comparison  A standard 2D browser: 100 nodes (w/3 character text strings)  Hyperbolic browser: 1000 nodes, about 50 nearest the focus can show from 3 to dozens of characters 2614 Fall 2013 CS 7450 1 2 5 4 3 Clicking on the blue node brings it into focus at the center 27 Fall 2013 CS 7450 Watch it Work • Video • Demo from prefuse system 2815 Fall 2013 CS 7450 Key Attributes • Natural magnification (fisheye) in center • Layout depends only on 2-3 generations from current node • Smooth animation for change in focus • Don’t draw objects when far enough from root (simplify rendering) 29 Fall 2013 CS 7450 Problems • What might be problems with this approach? 3016 Fall 2013 CS 7450 Problems • Orientation  Watching the view can be disorienting  When a node is moved, its children don’t keep their relative orientation to it as in Euclidean plane, they rotate  Not as symmetric and regular as Euclidean techniques, two important attributes in aesthetics 31 Fall 2013 CS 7450 How about 3D? • Can same hyperbolic transformation be applied, but now use 3D space? • Sure can • Have fun with the math! 3217 Fall 2013 CS 7450 H3Viewer Munzner, IEEE CG&A ‘98 Video 33 Fall 2013 CS 7450 Layout • Find a spanning tree from an input graph  Use domain-specific knowledge • Layout algorithm  Nodes are laid out on the surface of a hemisphere  A bottom-up pass to estimate the radius needed for each hemisphere  A top-down pass to place each child node on its parental hemisphere’s surface 3418 Fall 2013 CS 7450 Drawing • Maintain a target frame by showing less of the context surrounding the node of interest during interactive browsing • Fill in more of the surrounding scene when the user is idle 35 Fall 2013 CS 7450 Navigation Translation of a node to the center Rotation around the same node 3619 Fall 2013 CS 7450 Performance • Handle much larger graphs,