Transcription
Large Scale InformationVisualizationJing YangFall 20071Hierarchy and TreeVisualization21
Hierarchies Definition An ordering of groups in which larger groupsencompass sets of smaller groups. Data repository in which cases are related tosubcases3Hierarchies in the World Family histories, ancestries File/directory systems oncomputers Organization charts Object-oriented softwareclasses42
Good Hierarchy Visualization Allow adequate space within nodes to displayinformation Allow users to understand relationshipbetween a node and its context Allow to find elements quickly Fit into a bounded region Much more5Trees Hierarchies are often represented as trees Directed, acyclic graph Two major categories of tree visualizationtechniques: Node-link diagram Visible graphical edge from parents to theirchildrenSpace-filling63
Node-Link Diagrams7Node-Link Diagrams Root at top, leaves at bottom is very commonJ. Stasko’s InfoVis class slides84
Microsoft ExplorerWhat do you like and dislike about it?9Organization ChartA decision treeThe figure is from Barlow and Neville InfoVis 2001105
H-Tree Layout Work well only for binary treesHerman, G. Melançon, M.S. Marshall, “Graph Visualizationin Information Visualization: a Survey” In: IEEE Transactionson Visualization and Computer Graphics, 2000, pp. 24-44.11A Common VisualizationE. Kleiberg et. al. InfoVis 2001126
Different StylesRectangular: Well suited fordisplaying labeled/scaledtrees.Straight: Works well onlyon rooted binary trees.Smooth Edges: VeryRadial: Works well forsimilar to the rectangularvisualizing unrooted eepanel.html13A Classical Hierarchical ViewPosition children “below” their common ancestorsLayout can be top-down, left-to-right and grid like positioningFast: linear timeE. Reingold and J. Tilford. Tidier drawing of trees. IEEE Trans. Softw.Eng., SE-7(2):223-- 228, 1981147
Why Put Root at Top (Left) Root can be at centerwith levels growingoutward too Can any node be theroot?J. Stasko’s InfoVis class slides15Radial View Recursively positionchildren of a subtree into circularwedges the central angle ofthese wedges areproportional to thenumber of leavesP. Eades, “Drawing Free Trees”, Bulleting of the Institutefro Combinatorics and its Applications, 1992, pp. 10-36.168
Radial ViewInfovis contest 03 Treemap, Radial Tree, and 3D Tree Visualizations17Nihar et. al. Indiana UniversityBalloon View Siblings of sub-trees are included in circlesattached to the father node.Melancon, G., Herman, I.: Circular drawing of rooted trees. Reports ofthe Centre for Mathematics and Computer Sciences (CWI), INSR9817,189
Balloon ViewMelancon, G., Herman, I.: Circular drawing of rooted trees. Reports ofthe Centre for Mathematics and Computer Sciences (CWI), INSR9817,19The Challenges Scalability# of nodes increases exponentially Available space increases polynomially(circular case) Showing more attributes of data cases inhierarchy or focusing on particularapplications of trees Interactive exploration2010
3D TreeTavanti and Lind, InfoVis 0121Cone Tree Key ideas:Add a third dimension into which layout can go Compromise of top-down and centeredtechniques mentioned earlier Children of a node are laid out in a cylinder“below” the parent Siblings live in one of the 2D planes Robertson, Mackinlay, Card CHI ‘912211
Cone TreeRobertson, Mackinlay, Card CHI ‘9123Alternative ViewsRobertson, Mackinlay, Card CHI ‘912412
Advantages vs. Limitations Positive More effective area tolay out tree Use of smoothanimation to helpperson track updates Aesthetically pleasing Negative As in all 3D, occlusionobscures some nodes Non-trivial toimplement andrequires somegraphics horsepowerJ. Stasko’s InfoVis class slides25Hyperbolic Brower Key idea:Find a space (hyperbolic space) that increasesexponentially, lay out the tree on it Transform from the hyperbolic space to 2DEuclidean space J. Lamping and R. Rao, “The Hyperbolic Browser: A Focus ContextTechnique for Visualizing Large Hierarchies”, Journal of VisualLanguages and Computing, vol. 7, no. 1, 1995, pp. 33-55.2613
http://graphics.stanford.edu/ munzner/talks/calgary02272814
293015
Hyperbolic BrowerR. Spence. Information Visualization31Change Focus3216
Key Attributes Natural magnification (fisheye) in center Layout depends only on 2-3 generations fromcurrent node Smooth animation for change in focus Don’t draw objects when far enough from root(simplify rendering)J. Stasko’s InfoVis class slides33H3 Browser Use hyperbolic transformation in 3D spaceDemoTamara Munzner: H3: laying out large directed graphs in 3D hyperbolic space.34INFOVIS 1997: 2-1017
Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Basic idea: we can easily see the branches,leaves, and their arrangement in a botanicaltree Inspiration: Strand model of Holton Strands: internal vascular structure of abotanical treeNode and link diagramCorresponding strand Model35Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Use strand model to create a 3-d directorytree:Unsatisfied features: 1. Branching points 2. long and thinbranches 3. cluttered leaves3618
Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Improve the first tree:Adding smooth transition between two cylinders37Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Improve the first tree:Use a general tree rather than a binary tree3819
Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Improve the first tree:Phi-ball with one (left) and many (right) files39Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Botanical tree:Final model with the improvements4020
Botanical Tree [E. Kleiberg et. al. InfoVis 2001] Botanical tree:The same directory with different settings41Collapsible Cylindrical Tree [Dachselt& Ebert Infovis 01] Basic idea: use a set of nested cylindersaccording to the telescope metaphor Limitation: one path is visible in once Interactions: rotation, go down/up4221
Collapsible Cylindrical Tree [R.Dachselt, J. Ebert Infovis 01] Example application: web document browsing43Space-Filling Techniques4422
Space-Filling Techniques Each item occupies an area Children are “contained” within parent45Visualization of Large HierarchicalData by Circle Packing W.Wang et al. CHI 2006 Key ideas:tree visualization using nested circles brother nodes represented by externallytangent circles nodes at different levels displayed by using 2Dnested circles or 3D nested cylinders 4623
Visualization of Large HierarchicalData by Circle Packing W.Wang et al. CHI 200647Visualization of Large HierarchicalData by Circle Packing W.Wang et al. CHI 20064824
Visualization of Large HierarchicalData by Circle Packing W.Wang et al. CHI 200649Treemap Children are drawn inside their parents Alternative horizontal and vertical slicing ateach successive level Use area to encode other variables of dataitemsB. Johnson, Ben Shneiderman: Tree maps: A Space-Filling Approach to theVisualization of Hierarchical Information Structures. IEEE Visualization 1991:284-2915025
Treemap ExampleJ. Stasko’s InfoVis class slides51Treemap ExampleJ. Stasko’s InfoVis class slides5226
Treemap 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}J. Stasko’s InfoVis class slides53Treemap Affordances It is rectangular! Good representation of two attributes beyondnode-link: color and area Not as good at representing structureCan get long-thin aspect ratios What happens if it’s a perfectly balanced treeof items all the same size? 5427
Aspect ratios55J. Stasko’s InfoVis class slidesTreemap Variation Make rectangles more -sizeSquarifiedStrip5628
Showing StructureA tree with 698 node (from [Balzer:infovis2005]How about a perfectly balanced binary tree?57Showing Structure Borderless treemap: hard to discern structureof hierarchy What happens if it’s a perfectly balanced treeof items all the same size? Variations:Use border Change rectangles to other forms 5829
Nested vs. Non-nested59Non-nested TreemapNested TreemapNested Treemap Borders help onsmaller trees, buttake up too mucharea on large,deep emap97.shtml6030
Cushion Treemap Add shading and texture (Van Wijk and Vande Wetering InfoVis’99)61Voronoi Treemaps [balzer:infovis05] Enable subdivisions of and in polygons Fit into areas of arbitrary shape6231
Basic Voronoi Tessellations Enable partitioning of m-dimensional space withoutholes or overlappings Planar VT in 2D: P: {p1, .pn} a set of n distinct points –generatorsDivide 2D space into n Voronoi regions V(Pi): Any point q lies in the region V(Pi) if and only if distance(pi, q) distance(pj,q) for any j ! i63Weighted Voronoi Tessellations Basic VT: Additively weighted Voronoi (AW VT: Additively weighted power voronoi (PW VT):Left: AW VTRight: PW VT6432
Centroidal Voronoi Tessellations (CVT) Property of CVT: Each generator is itselfcenter of mass(centroid) of correspondingvoronoi region65Centroidal Voronoi Tessellations (CVT) CVT minimize the energy function: The energy of the CVT is equivalent to theoverall aspect ratio of the subareas of thetreemap layout6633
Voronoi Treemap Algorithm Size of each Voronoi region should reflect size of thetree node Area size is not observed in CVT computation Extension: Use iterationIn each iteration, adjust the area of regions by theirweightsWeights are adjusted according to the size of the nodeIterate until the relative size error is under a threshold Video67Treemap Applications Software visualization Multimedia visualization Tennis matches File/directory structures Basketball statistics Stocks and portfolios6834
tware Visualization SeeSys (Baker & Eick, AT&T Bell Labs)New codein thisrelease7035
Internet News Groups Netscan (Fiore & Smith Microsoft)71SequoiaView File visualizater www.win.tue.nl/sequoiaview/7236
Photemesa Image browser (quantum and bubble ce-Filling Techniques Each item occupies an area Children are “contained” within (under) parentOne Example7437
Icicle Plot Icicle plot (similar to Kleiner and Hartigan’sconcept of castles) Node size is proportional to node widthBarlow and Neville InfoVis 200175Radial Space Filing Techniques InterRing [Yang02]7638
Node Link SpaceFilling Techniques77Elastic Hierarchies: Combining Treemaps andNode-Link Diagrams [zhao:infovis 05] A hybrid approach Dynamic Video7839
Space-Optimized Tree - Motivation79Q. Nguyen and M. Huang Infovis 02Space-Optimized Tree [Q. Nguyen and M.Huang Infovis 02]Key idea: Partition display space into a collection of geometricalareas for all nodes Use node-link diagrams to show relational structureExample: Tree with 150 nodesExample: Tree with approximately8055000 nodes40
Space-Optimized Tree [Q. Nguyen and M.Huang Infovis 02]Algorithm for dividing a region:1. weight calculation for each direct child2. wedge calculation for each direct child3. vertex position calculation for each direct child81Weight Calculation Vi: the direct child Vl – Vl k : Direct children of Vi Constant C: decide difference betweenvertexes with more descendants andvertexes with fewer descendants.8241
Wedge CalculationExample of dividing the localregion of one node83Vertex Position CalculationArea ABCP Area AEDPVertex is the midpoint of line AP8442
Space-Optimized Tree85Example: Tree with approximately 55000 nodes43
Visualization of Large Hierarchical Data by Circle Packing W.Wang et al. CHI 2006 50 Treemap Children are drawn inside their parents Alternative horizontal and vertical slicing at each successive level Use area to encode other variables of data items B. Johnson, Be
