CSE 442 - Data Visualization Hierarchies

Transcription

CSE 442 - Data VisualizationHierarchiesJeffrey Heer University of Washington

Graphs and TreesToday: Visualizing Hierarchical DataNext Time: Visualizing Network DataGoalsOverview of layout approachesAssess strengths and weaknessesInsight into implementation techniques

Graphs and TreesGraphsModel relations among dataNodes and edgesTreesGraphs with hierarchical structureConnected graph with N-1 edgesNodes as parents and children

Spatial LayoutA primary concern of tree/graph drawing isthe spatial arrangement of nodes and edges.Often (but not always) the goal is toeffectively depict the graph structure:- Connectivity, path-following- Topological distance- Clustering / grouping- Ordering (e.g., hierarchy level)

Tree VisualizationIndentationLinear list, indentation encodes depthNode-Link diagramsNodes connected by lines/curvesEnclosure diagramsRepresent hierarchy by enclosureLayeringRelative position and alignmentTypically fast: O(n) or O(n log n), interactive layout

Interactive Layout Demo (requires Flash Player)

Tree Layout

IndentationPlaces all items alongvertically spaced rowsIndentation used to showparent/child relationshipsCommonly used as acomponent in an interfaceBreadth and depthcontend for spaceOften requires a greatdeal of scrolling

Single-Focus (Accordion) ListSeparate breadth & depth along 2D.Focus on a single path at a time.

Node-Link DiagramsNodes are distributed in space, connected bystraight or curved linesTypical approach is to use 2D space to breakapart breadth and depthOften space is used to communicate hierarchicalorientation (e.g., towards authority or generality)

Naïve Recursive LayoutRepeatedly divide space for subtrees by leaf count Breadth of tree along one dimension Depth along the other dimension

Naïve Recursive LayoutRepeatedly divide space for subtrees by leaf count Breadth of tree along one dimension Depth along the other dimensionProblem: exponential growth of breadth

Reingold & Tilford’s “Tidy” LayoutGoal: make smarter useof space, maximizedensity and symmetry.Originally binary trees,extended by Walker tocover general case.Corrected by Buchheimet al. to achieve a lineartime algorithm.

Reingold-Tilford LayoutDesign ConsiderationsClearly encode depth levelNo edge crossingsIsomorphic subtrees drawn identicallyOrdering and symmetry preservedCompact layout (don’t waste space)

Reingold-Tilford LayoutInitial bottom-up (post-order) traversal of the treeY-coordinates based on tree depthX-coordinates set piecemeal via “shifts” at each depthAt each parent node: merge left and right subtreesShift right subtree as close as possible to the leftComputed efficiently by maintaining subtree contours“Shifts” in position saved for each nodeParent nodes centered above childrenFinal top-down (pre-order) traversal to set X-coordinatesSum initial layout and aggregated shifts

Reingold-Tilford Layout1271162140385109

Reingold-Tilford Layout0

Reingold-Tilford Layout10

Reingold-Tilford Layout210

Reingold-Tilford Layout2103

Reingold-Tilford Layout21403

Reingold-Tilford Layout214035

Reingold-Tilford Layout214035

Reingold-Tilford Layout214035

Reingold-Tilford Layout214035

Reingold-Tilford Layout214035

Reingold-Tilford Layout6214035

Reingold-Tilford Layout6214035

Reingold-Tilford Layout6214035

Reingold-Tilford Layout6214035

Reingold-Tilford Layout76214035

Reingold-Tilford Layout762140385

Reingold-Tilford Layout7621403859

Reingold-Tilford Layout762140385109

Reingold-Tilford Layout762140385109

Reingold-Tilford Layout762140385109

Reingold-Tilford Layout762140385109

Reingold-Tilford Layout762140385109

Reingold-Tilford Layout71162140385109

Reingold-Tilford Layout71162140385109

Reingold-Tilford Layout71162140385109

Reingold-Tilford Layout71162140385109

Reingold-Tilford Layout71162140385109

Reingold-Tilford Layout1271162140385109

Cluster DendrogramsDepicts cluster treesproduced by hierarchicalclustering algorithms.Leaf nodes arranged in aline, internal node depthindicates order/value atwhich clusters merge.Naïve recursive layoutwith orthogonal twosegment edges.

Radial Tree LayoutNode-link diagram inpolar co-ordinates.Radius encodes depth,with root in the center.Angular sectors assignedto subtrees (often withnaïve recursive layout).Reingold-Tilford methodcan also be applied here.

Circular Tree LayoutLayout in 3D to formCone Trees.Balloon Trees can bedescribed as a 2Dvariant of a Cone Tree.Not just a flatteningprocess: circles mustnot overlap.

Focus Context

Visualizing Large Hierarchies Indented Layout Reingold-Tilford Layout

More Nodes, More Problems ScaleTree breadth often grows exponentiallyEven with tidy layout, quickly run out of spacePossible SolutionsFilteringFocus ContextScrolling or PanningZoomingAggregation

MC Escher, Circle Limit IV

Hyperbolic LayoutPerform tree layout inhyperbolic geometry,project the result on tothe Euclidean plane.Why? Like tree breadth,the hyperbolic planeexpands exponentially!Also computable in 3D,projected into a sphere.

Degree-of-Interest TreesSpace-constrained, multi-focal tree layout

Degree-of-Interest TreesRemove “low interest” nodes at a given depth leveluntil all blocks on a level fit within bounds.Attempt to center child blocks beneath parents.

Enclosure

Enclosure DiagramsEncode structure using spatial enclosurePopularly known as treemapsBenefitsProvides a single view of an entire treeEasier to spot large/small nodesProblemsDifficult to accurately read structure / depth

Circle Packing LayoutNodes are representedas sized circles.Nesting shows parentchild relationships.Issues?Inefficient use of space.Parent size misleading?

TreemapsHierarchy visualization that emphasizesvalues of nodes via area encoding.Partition 2D space such that leaf nodeshave sizes proportional to data values.First layout algorithms proposed byShneiderman et al. in 1990, with focus onshowing file sizes on a hard drive.

Slice & Dice layout: Alternate horizontal / vertical partitions.

Wattenberg 1998Squarifed layout: Try to produce square (1:1) aspect ratios

Squarified Treemaps [Bruls et al. ’00]Slice & Dice layout suffers from extreme aspectratios. How might we do better?Squarified layout: greedy optimization forobjective of square rectangles. Slice/dice withinsiblings; alternate whenever ratio worsens.vs.

Interactive Example

Why Squares?[Bruls et al. ’00]Posited Benefits of 1:1 Aspect Ratios1. Minimize perimeter, reducing border ink.Mathematically true!2. Easier to select with a mouse cursor.Validated by empirical research & Fitt’s Law!3. Similar aspect ratios are easier to compare.Seems intuitive, but is this true?

Comparison Error vs. Aspect RatioSquaresStudy by Kong, Heer & Agrawala, InfoVis ’10.Comparison of squares has higher error!“Squarify” works because it fails to meet its objective?

Why Squares?[Bruls et al. ’00]Posited Benefits of 1:1 Aspect Ratios1. Minimize perimeter, reducing border ink.Mathematically true!2. Easier to select with a mouse cursor.Validated by empirical research & Fitt’s Law!3. Similar aspect ratios are easier to compare.Seems intuitive, but is this true?

Why Squares?[Bruls et al. ’00]Posited Benefits of 1:1 Aspect Ratios1. Minimize perimeter, reducing border ink.Mathematically true!2. Easier to select with a mouse cursor.Validated by empirical research & Fitt’s Law!3. Similar aspect ratios are easier to compare.Extreme ratios & squares-only more inaccurate.Balanced ratios better? Target golden ratio?

Treemaps vs. Bar Charts [Kong et al. ’10]Position is generally more effective than area, but What happens when the element count gets high?What happens when comparing groups of elements,such as leaf values vs. internal node values?

Treemaps vs. Bar Charts [Kong et al. ’10]At low densities ( 4k elements), bar charts moreaccurate than treemaps for leaf-node comparisons.At higher density, treemaps led to faster judgments.Treemaps better for group-level comparisons.

Cushion Treemaps[van Wijk & Wetering ’99]Uses shading to emphasize hierarchal structure.

Cascaded Treemaps[Lü & Fogarty ’08]Uses 2.5D effect to emphasize hierarchy relations.

Voronoi Treemaps [Balzer et al. ’05]Instead of rectangles,create treemaps witharbitrary polygonalshapes and boundary.Use iterative, weightedVoronoi tessellations toachieve cells with valueproportional areas.

Iterative Voronoi Tesselations [Jason Davies]

Layering

Layered DiagramsSignify tree structure using:- Layering- Adjacency- AlignmentInvolves recursive sub-division of space.Leaf nodes may be sized by value, parent sizevisualizes sum of descendant leaf values.

Icicle Trees: Cartesian Partition

“Sunburst” Trees: Polar Partition

Layered Trees Useful Elsewhere

Hybrids

Hybrids are also possible “Elastic Hierarchies”Node-link diagramwith treemap nodes.Little uptake for realworld use

Administrivia

Final Project DeliverablesInteractive Web PageWorking (near-final) version due Wed 5/31.Final version due by showcase on Mon 6/5.Demonstration Video ( 2 min)Due Wed 5/31. We will show in-class on 6/1!Poster & Demo for Final ShowcaseMonday 6/5, 10:30am-1pm in Allen Center atrium.External judges will award top projects!Read assignment description for more!

Final Project ShowcaseWhen: Monday June 5, 10:30am - 1pm.Where: Allen Center AtriumThe event is open to the public. Invite your friends!Public showing begins at 11am. Arrive at 10:30amto set up your poster and demo. Be prepared togive a 3 min. presentation demo to visitors.Invited judges will rate & award the top projects.Refreshments will be served!

Tips for a Successful ProjectFocus on a compelling real-world use.Who is your user? How do you gauge success?Consider multiple design alternatives.Prototype quickly (use Tableau, R, Gephi ).Seek feedback (representative users, peers, ).Even informal usage can provide insights.Choose appropriate team roles.Start early (and read the suggested paper!)

Animated Transitionsin Tree Visualizations

Cone Trees[Robertson 91]

Polyarchies[Robertson 02]Animate pivots acrossintersecting hierarchies.Tested a number ofanimation parameters.Best duration: 1 secRotational movementdegraded performance,translation preferred.

Degree-of-Interest Trees[Heer 04]Animation of expanding/collapsing branches

Space Tree[Grosjean 04]Break animated transitions into discrete stages

Radial Graph LayoutOptimize animation to aid comprehensionhttp://people.ischool.berkeley.edu/ rachna/gtv/

Animation in Radial Graph LayoutHelp maintain context of nodes and generalorientation of user during refocus.Transition PathsLinear interpolation of polar coordinatesNode moves in an arc, not straight linesMoves along circle if not changing levelsWhen changing levels, spirals to next ring

Animation in Radial Graph LayoutTransition constraintsMinimize rotational travel (move former parentaway from new focus in same orientation)Avoid cross-over of edges

Retain Edge Orientation

Retain Neighbor Order

Summary: Tree VisualizationIndentationLinear list, indentation encodes depthNode-Link diagramsNodes connected by lines/curvesEnclosure diagramsRepresent hierarchy by enclosureLayeringRelative position and alignmentFocus Context techniques for scale!

Hierarchy visualization that emphasizes values of nodes via area encoding. Partition 2D space such that leaf nodes have sizes proportional to data values. First layout algorithms proposed by Shneiderman et al. in 1990,