Cours de Visualisation dInformationInfoVis LectureHierarchies and Trees 1Frdric VernierEnseignant-Chercheur LIMSI-CNRSMatre de conf Paris XI Inspired from CS 7450 - Information VisualizationJan. 10, 2002John StaskoFrom J. Stasko lecture - CS 7450 Spring 2002 Georgia TechHierarchiesDefinitionData repository in which cases are related to subcasesCan be thought of as imposing an ordering in which cases are parents or ancestors of other cases2From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechHierarchies in the WorldPervasiveFamily histories, ancestriesFile/directory systems on computersOrganization chartsAnimal kingdom: Phylum, genus,Object-oriented software classesSpecies historyY axis = timeIs it really discrete ? 3From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechTreesHierarchies often represented as treesDirected, acyclic graphTwo main representation schemesNode-link (1/2)Space-filling (2/2)4From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechNode-Link DiagramsRoot at top, leaves at bottom is very commonOr left-rightAligned / no brotherhood5From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechSample RepresentationJohnson & Shneiderman, 916From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechExamplesGood for?Bad for? SearchUnderstanding structure7From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechWhy Put Root at Top?Root can be atcenter with levelsgrowing outwardtooCan any nodebe the root?Pre-attentively ?8From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechDrawing a TreeHow does one draw this? DFS Percolate requirements upward9From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechPotential ProblemsFor top-down, width of fan-out uses up horizontal real estate very quicklyAt level n, there are 2n nodes for binary treeTree might grow a lot along one particular branchHard to draw it well in view without knowing how it will branch10From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechInfoVis SolutionsTechniques developed in Information Visualization largely try to assist the problems identified in the last slideAlternatively, Information Visualization techniques attempt to show more attributes of data cases in hierarchy or focus on particular applications of trees11From J. Stasko lecture - CS 7450 Spring 2002 Georgia Tech3D ApproachesAdd a third dimension into which layout can goCompromise of top-down and centered techniques mentioned earlierChildren of a node are laid out in a cylinder “below” the parentSiblings live in one of the 2D planes12From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechCone TreesDeveloped atXerox PARC3D views ofhierarchiessuch as filesystemsRobertson, Mackinlay, Card 9113From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechAlternate Views14From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechCone TreesPositiveMore effective area to lay out treeUse of smooth animation to help person track updatesAesthetically pleasingNegativeAs in all 3D, occlusion obscures some nodesNon-trivial to implement and requires some graphics horsepowerRead in perspectiveDifficult if too muchAnti-aliasing = more horsepowerBigger font = lost of screen real estate15From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechAlternative SolutionsChange the geometryApply a hyperbolic transformation to the spaceRoot is at center, subordinates aroundApply idea recursively, distance decreases between parent and child as you move farther from center, children go in wedge rather than circle16From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechHyperbolic BrowserFocus + Context TechniqueDetailed view blended with a global viewFirst lay out the hierarchy on the hyperbolic planeThen map this plane to a diskStart with the trees root at the center Use animation to navigate along this representation of the planeLamping and Rao, 9417From J. Stasko lecture - CS 7450 Spring 2002 Georgia Tech2D Hyperbolic BrowserApproach: Lay out the hierarchy on the hyperbolic plane and map this plane onto a display region.ComparisonA 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 characters18From J. Stasko lecture - CS 7450 Spring 2002 Georgia Tech12543Clicking on the bluenode brings it into focus at the center19From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechWatch it WorkDemo from Inxight web site20From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechKey AttributesNatural magnification (fisheye) in centerLayout depends only on 2-3 generations from current nodeSmooth animation for change in focusDont draw objects when far enough from root (simplify rendering)21From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechProblemsOrientationWatching the view can be disorientingWhen a node is moved, its children dont keep their relative orientation to it as in Euclidean plane, they rotateNot as symmetric and regular as Euclidean techniques, two important attributes in aesthetics22From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechHow about 3D?Can same hyperbolic transformation be applied, but now use 3D space?Sure canHave fun with the math!23From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechH3ViewerMunzner, 98Video24From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechLayoutFind a spanning tree from an input graphUse domain-specific knowledgeLayout algorithmNodes are laid out on the surface of a hemisphereA bottom-up pass to estimate the radius needed for each hemisphereA top-down pass to place each child node on its parental hemispheres surface 25From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechDrawingMaintain a target frame by showing less of the context surrounding the node of interest during interactive browsingFill in more of the surrounding scene when the user is idle26From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechNavigationTranslation of a node to the centerRotation around the same node27From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechPerformanceHandle much larger graphs, i.e. 100,000 edges Support dynamic exploration & interactive browsingMaintain a guaranteed frame rate http:/graphics.stanford.edu/munzner/28From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechSee the Forest.How about collections of trees? (Forests)Multitrees (M-trees)“A class of directed acyclic graphs (DAGs) (that) have large easily identifiable substructures that are trees.”M-trees are DAGs, not trees, butFurnas & Zacks, 9429From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechMultitrees are DAGsCan be built by adding new tree structure above existing subtreesThe descendants of any node form a tree of contentsDiamonds are (mostly) not permittedThe ancestors of any node form a tree of contexts30From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechExample31From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechComposition32From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechNo DiamondsDiamonds are not permittedOccurs when there are 2 distinct directed paths between 2 nodes.At most one directed path between 2 nodes.33From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechMultitrees contain Topological TreesTopological tree or t-tree: an undirected graph, that is a connected graph without cyclesM-trees are not t-trees; they have undirected cyclesHowever, m-trees contain large t-trees.The ancestors and descendants of a unique path is a t-tree34From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechCentrifugal ViewA view of the ancestors (context) and descendants (children) of an individual (interior) nodeTransitions between centrifugal views can be animated35From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechCentrifugal ViewDirections36From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechContents Fisheye ViewDownward tree of contents rooted at the context “User JMZ”37From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechContexts Fisheye ViewInverted tree of contexts rooted at the content “Directions”38From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechIntegrated Fisheye View39From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechDiamonds Are ForeverSometimes, diamonds will not go awayPeople want to put the same item in more than one place in the tree.A set of documents organized both alphabetically and by dateTelephone directory designed for lookup by name or by phone numberOrganize sub-m-trees beneath more general structures at the diamond level40From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechOrganization of RootsNo top-down structure over the set of all rootsTo guarantee a view of all roots, introduce an “artificial” leaf (descendant of all roots), whose upward view (by design) is a tree of all roots41From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechMultitree IssuesReuse out of contextWhen constructing a m-tree, fragments may not hang togetherAdd or include new fragments to relate pieces in the new m-treeConstructionBy hand is the most common way.Perhaps automatic, along hypertext links, so long as no 2 hyperlink paths lead back to the same page!42From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechFood for ThoughtWhich of these techniques are useful for what purpose?How well do they scale?What if we want to portray more variables of each case?43From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechReferencesSpence and CMS textsAll referred to papersCai & Krohne and Pan & Wang F 99 slides44From J. Stasko lecture - CS 7450 Spring 2002 Georgia TechUpcomingSpace-filling tree representationsGraphs and networks45