1Hierarchies and Trees 1(Node-link)CS 4460/7450 - Information VisualizationMarch 4, 2010John StaskoSpring 2010 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 2010 CS 4460/7450Hierarchies in the World• Pervasive Family histories, ancestries File/directory systems on computers Organization charts Animal kingdom: Phylum,…, genus,… Object-oriented software classes ...3Spring 2010 CS 4460/7450Trees• Hierarchies often represented as trees Directed, acyclic graph• Two main representation schemes Node-link (today) Space-filling43Spring 2010 CS 4460/7450Node-Link Diagrams• Root at top, leaves at bottom is very common5Spring 2010 CS 4460/7450Sample RepresentationFrom: Johnson & Shneiderman, „9164Spring 2010 CS 4460/7450ExamplesGood for?Bad for? SearchUnderstandingstructure7Spring 2010 CS 4460/7450Why Put Root at Top?Root can be atcenter with levelsgrowing outwardtooCan any nodebe the root?85Spring 2010 CS 4460/7450Drawing a TreeHow does one draw this?• DFS• Percolate requirements upward9Spring 2010 CS 4460/7450Potential 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 branch106Spring 2010 CS 4460/7450InfoVis 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 trees11Spring 2010 CS 4460/7450SpaceTree• Uses conventional 2D layout techniques with some clever additionsGrosjean, Plaisant, BedersonInfoVis „02Video & Demo127Spring 2010 CS 4460/7450Characteristics• Vertical or horizontal• Subtrees are triangles Size indicates depth Shading indicates number of nodes inside• Navigate by clicking on nodes Strongly restrict zooming13Spring 2010 CS 4460/7450Design Features• Make labels readable• Maximize number of levels opened • Decompose tree animation• Use landmarks• Use overview and dynamic filtering148Spring 2010 CS 4460/74503D 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 planes15Spring 2010 CS 4460/7450Cone TreesVideoDeveloped atXerox PARC3D views ofhierarchiessuch as filesystemsRobertson, Mackinlay, Card CHI „91169Spring 2010 CS 4460/7450Alternate Views17Spring 2010 CS 4460/7450Cone Trees• Positives & negatives? Discuss1810Spring 2010 CS 4460/7450Cone Trees• Positive More effective area to lay out tree Use of smooth animation to help person track updates Aesthetically pleasing• Negative As in all 3D, occlusion obscures some nodes Non-trivial to implement and requires some graphics horsepower19Spring 2010 CS 4460/7450Alternative 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 circle2011Spring 2010 CS 4460/7450Hyperbolic 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 planeLamping and Rao, JVLC „9621Spring 2010 CS 4460/74502D 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 characters2212Spring 2010 CS 4460/745012543Clicking on the bluenode brings it into focus at the center23Spring 2010 CS 4460/7450Watch it Work• Video• Demo from prefuse system2413Spring 2010 CS 4460/7450Key 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)25Spring 2010 CS 4460/7450Problems• What might be problems with this approach?2614Spring 2010 CS 4460/7450Problems• 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 aesthetics27Spring 2010 CS 4460/7450How about 3D?• Can same hyperbolic transformation be applied, but now use 3D space?• Sure can• Have fun with the math!2815Spring 2010 CS 4460/7450H3ViewerMunzner, IEEE CG&A „98Video29Spring 2010 CS 4460/7450Layout• 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 3016Spring 2010 CS 4460/7450Drawing• 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 idle31Spring 2010 CS 4460/7450NavigationTranslation of a node to the centerRotation around the same node3217Spring 2010 CS 4460/7450Performance• Handle much larger graphs, i.e. >100,000 edges • Support dynamic exploration & interactive browsing• Maintain a guaranteed frame ratehttp://graphics.stanford.edu/~munzner/33Spring 2010 CS 4460/7450Old School• After all the interest in 3D and hyperbolic techniques in the ‟90‟s, recently, there has been renewed interest in the old 2D methods (just done better) SpaceTree presented earlier Next 3 papers…3418Degree-of-Interest Trees• Problem: Trees quickly degrade into line• Approach: Use fisheye-like focus & context ideas to control how a tree is drawnSpring 2010 CS 4460/7450Card &