Member, IEEE Niklas Elmqvist

Member, IEEE Jean-Daniel Fekete
email: jean-daniel.fekete@inria.fr.

Hierarchical Aggregation for Information Visualization: Overview, Techniques and Design Guidelines

Keywords: Aggregation, clustering, clutter reduction, massive datasets, visual exploration, visual analytics

We present a model for building, visualizing, and interacting with multiscale representations of information visualization techniques using hierarchical aggregation. The motivation for this work is to make visual representations more visually scalable and less cluttered. The model allows for augmenting existing techniques with multiscale functionality, as well as for designing new visualization and interaction techniques that conform to this new class of visual representations. We give some examples of how to use the model for standard information visualization techniques such as scatterplots, parallel coordinates, and node-link diagrams, and discuss existing techniques that are based on hierarchical aggregation. This yields a set of design guidelines for aggregated visualizations. We also present a basic vocabulary of interaction techniques suitable for navigating these multiscale visualizations.

INTRODUCTION

OVERVIEW is one of the most basic user tasks for information visualization [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF] and it is a vital building block for the more complex process of visual exploration-using visualization to form, test, and validate hypotheses about complex or large datasets [START_REF] Keim | Information visualization and visual data mining[END_REF]. However, overview is becoming increasingly difficult to effectively achieve with the ever-increasing size of real-world datasets. For most basic visualization techniques that endeavor to show each item in a dataset-such as scatterplots [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF], parallel coordinates [START_REF] Inselberg | The plane with parallel coordinates[END_REF], and treemaps [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF]-a massive number of items will overload the visualization, resulting in clutter that both causes technical scalability problems [START_REF] Fekete | Interactive information visualization of a million items[END_REF] as well as hinders the user's understanding of its structure and contents [START_REF] Cui | Measuring data abstraction quality in multiresolution visualizations[END_REF][START_REF] Peng | Clutter reduction in multi-dimensional data visualization using dimension reordering[END_REF].

New visualization techniques, such as dense pixel displays [START_REF] Keim | Designing pixel-oriented visualization techniques: Theory and applications[END_REF], have been proposed for dealing with large datasets, but most of these approaches still attempt to draw each item in the dataset. This is not practical for massive datasets. Another solution to this data overload problem, be it technical or perceptual in nature, is to introduce abstraction that reduces the amount of items to display, either in data space or in visual space [START_REF] Cui | Measuring data abstraction quality in multiresolution visualizations[END_REF]; examples include hierarchical parallel coordinates [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF], color histograms [START_REF] Elmqvist | DataMeadow: A visual canvas for analysis of large-scale multivariate data[END_REF][START_REF] Elmqvist | DataMeadow: a visual canvas for analysis of large-scale multivariate data[END_REF], and clustered time-series data [START_REF] Van Wijk | Cluster and calendar based visualization of time series data[END_REF].

In this article, we draw from this existing work on data abstraction to present a model for transforming virtually any visualization technique into a multiscale structure using hierarchical aggregation. The model is based on coupling aggregation in data space with a corresponding visual representation of the aggregation as a visual entity in the graphical space. This visual aggregate can convey additional information about the underlying contents, such as an average value, minima and maxima, or even its data distribution. Any visualization technique that implements this basic model becomes a multiscale structure, and can be interacted with using generic interaction techniques for multiscale navigation. In this article, we attempt to unify the design space for this class of visualization techniques, showing implementations for a number of visual representations such as scatterplots, parallel coordinates, and node-link diagrams. We also give a basic vocabulary of interaction techniques for aggregated visualizations.

There are several benefits to having this kind of model: (i) it represents a way to turn existing visualization techniques into multiresolution versions that scale better to massive datasets; (ii) it suggests a method for designing new visualization techniques that directly support multiresolution functionality; and (iii) it gives users a unified way

RELATED WORK

Data abstraction for the purposes of reducing visual clutter and dataset size is not a novel idea. Shneiderman's taxonomy of information visualization tasks [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF] touches upon important data abstraction operations such as filter and zoom as well as the importance of an overview. Oliveira and Levkowitz [START_REF] De Oliveira | From visual data exploration to visual data mining: A survey[END_REF] survey the use of visualization for data mining and discuss some standard data mining techniques for abstracting large-scale datasets, including dimension reduction (e.g., Principal Component Analysis [START_REF] Anderson | An Introduction to Multivariate Statistical Analysis[END_REF]), subsetting (e.g., random sampling [START_REF] Dix | By chance -enhancing interaction with large data sets through statistical sampling[END_REF][START_REF] Olken | Simple random sampling from relational databases[END_REF]), segmentation (e.g., cluster analysis [START_REF] Jain | Data clustering: A review[END_REF][START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF]), and aggregation. Our work in the present article is based on the latter technique-hierarchical aggregation of data items, where the original data items are used to create new and aggregated items.

Andrienko and Andrienko [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF] give a coherent treatment of data aggregation and its statistical foundations in exploratory data analysis [START_REF] Tukey | Exploratory data analysis[END_REF], including a wide range of examples and techniques. On a related note, Billard and Diday [START_REF] Billard | Symbolic Data Analysis: Conceptual Statistics and Data Mining[END_REF] introduce symbolic data analysis for statistical analysis of very large datasets. Many of the techniques described in the present article draw inspiration from this large body of knowledge, but our focus here is on hierarchical aggregation that support more dynamic visual exploration as opposed to the static aggregations traditionally employed in statistics. These techniques can often be adapted for hierarchical aggregation, both in data and in visual space.

Most recently, Ellis and Dix [START_REF] Ellis | A taxonomy of clutter reduction for information visualisation[END_REF] present a taxonomy that captures virtually all aspects and strategies of data abstraction for visualization. They identify 11 different strategies for data abstraction and give examples of each, classifying existing work into an annotated taxonomy using a set of criteria derived from the literature. Their approach involves three rough groupings of strategies: appearance (affecting the visual representation of individual data items), spatial distortion (displacing visual data items), and temporal (animation).

However, the work of Ellis and Dix ignores the potentially useful distinction between performing abstraction in data space and in visual space that is highlighted by Cui et al. [START_REF] Cui | Measuring data abstraction quality in multiresolution visualizations[END_REF]. More specifically, some abstraction methods-including filtering [START_REF] Shneiderman | Dynamic queries for visual information seeking[END_REF], clustering [START_REF] Jain | Data clustering: A review[END_REF][START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF], and sampling [START_REF] Dix | By chance -enhancing interaction with large data sets through statistical sampling[END_REF]-operate on the actual items in the dataset, whereas others-such as distortion [START_REF] Leung | A review and taxonomy of distortionoriented presentation techniques[END_REF] and zooming [START_REF] Perlin | Pad: An alternative approach to the computer interface[END_REF]-affect the visual presentation of the items. However, many authors fail to acknowledge the benefit of providing a link between abstraction methods in data space and their representation in visual space.

Drawing visual representations of abstractions performed in data space support creating simplified versions of a visualization while still retaining the general overview [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF]. By dynamically changing the abstraction parameters, the user can also retrieve details-on-demand [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF]. Some existing work is based on this kind of visual aggregates; many of these techniques are presented in the body of this article in the relevant sections. To give a representative sampling, much of the inspiration for this article comes from the opacity representation of cluster results in parallel coordinates and starglyphs by Fua et al. [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF], edge aggregation in adjacency matrices by Elmqvist et al. [START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF], and hierarchical edge bundles for node-link diagrams by Holten [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF] (although the latter is not strictly a hierarchical aggregation technique).

Yang et al. [START_REF] Yang | Interactive hierarchical displays: a general framework for visualization and exploration of large multivariate data sets[END_REF] present a framework for interactive hierarchical displays that bears much resemblance to our work. In particular, they present hierarchical implementations for parallel coordinates [START_REF] Inselberg | The plane with parallel coordinates[END_REF], starplots [START_REF] Siegel | The surgical implication of physiologic patterns in myocardial infarction shock[END_REF], scatterplot matrices [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF], and dimensional stacking [START_REF] Leblanc | Exploring N-dimensional databases[END_REF].

However, unlike our model, their framework is designed solely for multivariate datasets and specifies a concrete visual representation and color coding for the aggregates. Therefore, our model is slightly more general, although by virtue of being more general, we also provide less guidance in actually implementing new multiscale visualizations.

As for the technical challenges of large-scale datasets, Fekete and Plaisant [START_REF] Fekete | Interactive information visualization of a million items[END_REF] show how to overcome them for datasets on the order of 10 6 items using scatterplots and treemaps. However, their approach is to preserve all visible items in the visualizations without any data abstraction, so while their findings-as well as similar findings on the scalability of visualization-are useful for tool architects, they are not directly relevant to the more conceptual nature of this work.

HIERARCHICAL AGGREGATION FOR VISUALIZATION

Our model for hierarchical aggregation in visualization is based on aggregation in data space and corresponding simplified visual representations of the aggregates in visual space. Essentially, the aggregation process turns any visualization into a multiscale structure that can be rendered at any desired level-of-detail. This provides the user with a manageable overview that hides any clutter arising from details in the dataset while still giving a reasonable indication of the data size, extents, or distribution through the visual aggregates. A set of basic interaction techniques support navigating this structure. The visual aggregates can convey different information about the underlying data items, such as their average, extents, or even their distribution. Furthermore, the interaction allows the user to drill down and retrieve details on-demand. In this way, hierarchically aggregated visualiza-tion techniques directly support the visual information seeking mantra: "overview first, zoom and filter, then details on demand." [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF] In this section, we present two main types of information visualizations, describe the basic aggregation model, discuss suitable visual representations, explain the rendering process of aggregate hierarchies, and give a basic set of interaction techniques for controlling this class of visualization techniques. Note that while this is a generalized model, there exist many special cases for specific visualizations. We will discuss these in the visualization examples following this section.

Terminology

For the purposes of hierarchical aggregation, it is useful to distinguish between two main types of visualizations: overlapping versus spacefilling visualizations [START_REF] Fekete | Interactive information visualization of a million items[END_REF]:

• Overlapping visualizations. A visualization type that enforces no layout restrictions on visual items, and items may thus overlap on the display (potentially causing occlusion). Overlapping visualizations include scatterplots, node-link diagrams, and parallel coordinates.

• Space-filling visualizations. A visualization that restricts layout to fill the available space and to avoid overlap. This means that individual visual data items do not occlude each other. Representative techniques include treemaps, most 2D and 3D geometric visualizations, and adjacency matrices.

In the following text, we will also use the term aggregate hierarchy (or aggregate tree) to mean a grouping of the original data items into a hierarchical structure of data aggregates, each representing their children. Visual aggregates are the graphical depictions of data aggregates, whereas visual items are graphical representations of data items. As a common term for both aggregates and items, we use visual entity.

Finally, given the above terms, we define visual entity budget as an upper limit of the number of visual entities to render for a particular hierarchically aggregated visualization. By controlling this limit, we can either use it to ensure a minimum frame rate by capping the amount of visual entities to draw, or to control the amount of visual clutter for the purposes of efficiently perceiving the visualized data.

Aggregation

Given a set of data items, hierarchical aggregation is based on iteratively building a tree of aggregate items either bottom-up or top-down. Each aggregate item consists of one or more children; either the original data items (leaves) or aggregate items (nodes). The root of the tree is an aggregate item that represents the whole dataset.

Bottom-up aggregation [START_REF] Jain | Data clustering: A review[END_REF][START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF] other hand, starts with one aggregate containing all the items and repeatedly splits aggregates until a specific level of granularity has been reached, or all items belong to only one aggregate. The common denominator between these two approaches is a similarity measure defined using a data-specific distance function.

There are several specific algorithms to perform aggregation. The most common are clustering approaches, such as graph-based or kmeans clustering [START_REF] Jain | Data clustering: A review[END_REF][START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF], but other examples include quadtree-and octree-based methods, such as the recursive merging of four adjacent edges into a single edge as done by Elmqvist et al. [START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF]. For cases where no suitable clustering method can be found, a good fallback may be to use data cube aggregation [START_REF] Stolte | Multiscale visualization using data cubes[END_REF] (similar to PivotGraph [START_REF] Wattenberg | Visual exploration of multivariate graphs[END_REF]) to easily turn a multivariate dataset into a hierarchical structure.

In order to make use of this aggregate tree, visualization techniques that support hierarchical aggregation provide not only a visual representation for the actual data items, but also for the aggregate items.

The aggregate tree becomes a multiscale structure for controlling the current level-of-detail of the visualization on the screen. Depending on the visualization technique, the visual aggregate can also convey information about the underlying data items (see the next section).

Visual Representation

Standard visualization techniques define a visual representation for individual data items (henceforth called visual data items), but a hierarchical aggregated visualization must also define a visual representation for data aggregates. This visual aggregate should convey something about the underlying data aggregation that the entity captures. It should also be distinguishable from visual data items (although this is not always the case). The type and amount of information conveyed depends on the visualization technique, but as a rule of thumb, the information should be simplified so as not to give rise to the same kind of visual clutter that we are trying to avoid.

Here are some examples of information that can be conveyed through visual aggregates (see [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF][START_REF] Billard | Symbolic Data Analysis: Conceptual Statistics and Data Mining[END_REF] for in-depth details):

• Count/sum: The number or the sum of the aggregated data items.

• Average: The arithmetic mean of the underlying data items (the color shading in Figure 8 shows the average point of each hull).

• Mode: The most frequent value in the underlying data set (most useful for discrete values).

• Extents: The extrema (minimum and maximum) of the underlying data items (Figure 1(b) shows the bounding boxes for each visual aggregate).

• Median: The value that divides the underlying data into two, equal-sized subsets. The median, and other positional measures, is often more robust against outliers than the average.

• Percentiles: The 25th, 50th (median), and 75th percentiles for the underlying data (such as the Tukey box in Figure 16).

• Distribution: The full distribution of the underlying data, often visualized using a histogram (Figure 11).

For non-numeric data items, we can still use several of the above symbolic metrics, including count, mode, and frequency distribution.

Rendering

Rendering a hierarchical aggregated visualization amounts to traversing the visual aggregate hierarchy. The traversal should typically be breadth-first to resolve depth ordering so that higher-level aggregates are correctly occluded by lower (more detailed) levels. This also allows for aborting the rendering at any stage, such as for maintaining a fixed frame rate, while still retaining a consistent visual output.

The visualization keeps track of the current detail level it is being viewed at, corresponding to the height in the tree to traverse to while rendering. Depending on the current state of the visualization, there are four main types of rendering traversals (Figure 2):

• Above traversal: All nodes above (and including) the current height are rendered. Here, data items are abstracted by highlevel visual aggregates, hiding details to avoid perceptual and technical overload (Figure 2(a)).

• Below traversal: All nodes below (and including) the current height are rendered. Less common, this gives an indication of how data items are grouped together (Figure 2(b)).

• Level traversal: All nodes on the same level as the current height are rendered. This gives a snapshot of the data abstraction at any specific detail level (Figure 2(c)).

• Range traversal: All nodes in an interval of levels are rendered. As for level traversal, range traversals give a snapshot of the data abstraction at a specific level, as well as some additional detail on the underlying aggregate hierarchy (Figure 2(d)). Beyond this, it is always possible to perform unbalanced traversals of the aggregate tree, e.g., to give details-on-demand to certain branches of the tree without traversing into neighboring branches. In particular, we could let the underlying variability of each aggregate automatically guide the rendering traversal [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF]. This would devote more detail to the "interesting" parts of a dataset, where there is a lot of varying features in the data, and save the entity budget in areas with low variance.

Unbalanced rendering traversals can also be used to support generalized fisheye views [START_REF] Furnas | Generalized fisheye views[END_REF]. This is done by letting the budget take a level of detail weight [START_REF] Furnas | Generalized fisheye views[END_REF][START_REF] Plaisant | SpaceTree: Supporting exploration in large node link tree, design evolution and empirical evaluation[END_REF] associated with the structure into account.

Clearly, the benefit of a data aggregate hierarchy and a corresponding visual aggregate hierarchy is that the resulting visualization can be adapted to the requirements of the human user as well as the technical limitations of the visualization platform. Instead of drawing an entire dataset as individual data items, a visualization technique supporting hierarchical aggregation can maintain a visual entity budget and only do a breadth-first traversal into the aggregate hierarchy until the budget has been expended. Since any visual aggregate at any level in the tree is guaranteed to serve as a faithful abstraction of underlying levels, the resulting image will remain consistent with the actual data.

Interaction

Beyond uniform methods for aggregation and rendering, one of the main benefits of hierarchical aggregated visualizations is that they can be made to support the same set of basic interaction techniques for navigating and manipulating the aggregate hierarchy. This allows users to apply the same reasoning and interaction strategies to different visualization techniques that support hierarchical aggregation. Here we will discuss a basic set of common interaction techniques for this purpose.

Note that while this article mainly focuses on developing new visualization techniques that support hierarchical aggregation, the space is also open for designing new interaction techniques for interacting with them. Hopefully, the presentation here will also serve as a useful framework for such activities.

For each of the interaction techniques in this section, we will use a combination of space-scale diagrams [START_REF] Furnas | Space-scale diagrams: Understanding multiscale interfaces[END_REF] and the aggregate hierarchy to describe the mechanics of the interaction. We will also give concrete examples of each interaction in existing systems and techniques. Because these interaction techniques mainly deal with various ways of navigating hierarchies (which is what an aggregate tree actually is), many of these techniques can also be found in tree visualization tools like treemaps [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF], Sunburst [START_REF] Stasko | An evaluation of space-filling information visualizations for depicting hierarchical structures[END_REF], and InterRing [START_REF] Yang | InterRing: An interactive tool for visually navigating and manipulating hierarchical structures[END_REF].

Zoom and Pan

Zooming and panning changes the current view of a visualization, respectively changing the size and position of the viewport window on the visual substrate [START_REF] Furnas | Space-scale diagrams: Understanding multiscale interfaces[END_REF][START_REF] Perlin | Pad: An alternative approach to the computer interface[END_REF] (Figure 3). In a way, zoom and pan operations can be seen as spatial filters that control which visual data entities to display on the screen as well as the screen space allocated to each entity. These operations are typically used to take a closer look at parts of a visualization without actually revealing more detail in the data. Navigation in multiscale spaces has recently been a focus in the human-computer interaction community because of its applicability to high-precision selection [START_REF] Guiard | Target acquisition in multiscale electronic worlds[END_REF][START_REF] Guiard | Navigation as multiscale pointing: Extending fitts' model to very high precision tasks[END_REF]. Many of these interaction techniques-such as speed-dependent automatic zooming (SDAZ) [START_REF] Igarashi | Speed-dependent automatic zooming for browsing large documents[END_REF], Zliding [START_REF] Ramos | Zliding: fluid zooming and sliding for high precision parameter manipulation[END_REF], and OrthoZoom [START_REF] Appert | OrthoZoom scroller: 1D multi-scale navigation[END_REF]-could be used to navigate the multiscale structures defined by the hierarchical aggregated visualizations discussed in this article.

Fua et al. [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF] describe a specialization of zooming for parallel coordinates that they call dimension zooming where each dimension axis is zoomed independently; this approach can easily be employed for other visualization techniques, such as using different axis scales in scatterplots or trivially for space-filling techniques such as treemaps. On the other hand, it does not make sense for visualizations where spatial location has no intrinsic meaning, such as for node-link diagrams.

On a related note, the snap-zoom [START_REF] Blanch | Browsing zoomable treemaps: Structureaware multi-scale navigation techniques[END_REF] technique is a variant of axisindependent zooming for continuous treemap navigation where the scale factor for the axes depends on a view-dependent (e.g. dynamically changing) layout criteria. This is a good example of how to customize a general interaction technique to the characteristics of a specific visualization while still retaining the same interaction pattern.

For the purpose of balancing zoom and pan operations, the work of van Wijk and Nuij [START_REF] Van Wijk | Smooth and efficient zooming and panning[END_REF] on smooth and efficient zooming and panning is particularly relevant. They present a computational model that can be used to control the speed and behavior of animated transitions from different viewports on a large visual space. However, this is clearly not relevant when the viewer has direct control over zooming and panning.

Drill-down and Roll-up

While zoom and pan merely control the geometric properties of the display, the drill-down and roll-up operations govern the level of detail at which the data is displayed [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF] (Figure 4). In other words, drill-down moves the rendering traversal deeper into the aggregate hierarchy, showing increasing amounts of detail, whereas roll-up moves up in the hierarchy, showing less detail. These operations are usually coupled with above rendering traversals of the aggregate hierarchy, although level traversals can be used to show a specific level in the hierarchy, and below traversals for showing the aggregation structure. In some cases, drilling and rolling should be restricted to the current geometric zoom and pan, or coupled with geometric zoom (see Section 3.5.5): drilling down further may not make sense if individual visual entities become smaller than a single pixel, and rolling may analogously not be useful if the entities become larger than the screen.

While geometric zoom is typically implemented as continuous [START_REF] Furnas | Space-scale diagrams: Understanding multiscale interfaces[END_REF], the level-of-detail of an aggregated visualization is clearly discrete. To facilitate user perception of the interaction technique changing the detail level, animated transitions between aggregation levels, like in the Matrix Zoom [START_REF] Abello | Matrix Zoom: A visual interface to semiexternal graphs[END_REF] system, can come in useful.

Many times, the viewer may want to perform drilling and rolling on a specific subtree of the aggregation hierarchy instead of on the whole tree. See the next section for more details.

Local Aggregation Control

As discussed in Section 3.4, it is sometimes useful to perform unbalanced rendering of the aggregate hierarchy to reveal different amounts of detail for different regions of the visualization in a fo-cus+context [START_REF] Furnas | Generalized fisheye views[END_REF][START_REF] Furnas | A fisheye follow-up: further reflections on focus + context[END_REF] fashion (Figure 5). Local aggregation control gives the user control over this process in different ways. For example, one form of local aggregation control may be to allow the user to directly select which part of the aggregate hierarchy to expand or collapse by, for example, simply clicking on the visual aggregates in the display (left-click for expand, right-click for collapse). Another instance of this type of interaction may include directly controlling the type of rendering traversal (Section 3.4) to perform, or parameters of the current traversal (cutoffs, start points, current level, etc).

In this case, selecting the region of interest becomes part of the problem. While rubberband selection in screen space is the most common approach, structure-based brushes [START_REF] Fua | Navigating hierarchies with structure-based brushes[END_REF] support filtering whole branches of the aggregate hierarchy based on its structure. Chuah [START_REF] Chuah | Dynamic aggregation with circular visual designs[END_REF] describe the use of Magic Lenses [START_REF] Bier | Toolglass and Magic Lenses: The see-through interface[END_REF] for local aggregation control. On a related note, the dynamic masking [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF] technique interactively fades out unselected regions in favor of selected regions.

Flipping

If drill-down and roll-up are the aggregate hierarchy equivalents of geometric zoom, then flipping [START_REF] Blanch | Browsing zoomable treemaps: Structureaware multi-scale navigation techniques[END_REF] is the equivalent of geometric pan (Figure 6). A discrete navigation operation, flipping lets the user visit neighboring siblings in the aggregate hierarchy (as opposed to nodes above or below in the hierarchy). Note that the effect of a flip operation is a geometrical pan because the operation changes the view of the visualization and not the aggregation level. However, as opposed to a normal pan, flipping is informed by the aggregate hierarchy. To make the transition between siblings easier for the user to follow, it is typically performed using an animation. This interaction makes the most sense for visualizations (typically space-filling) where spatial containment and adjacency is welldefined, as opposed to visualizations-such as scatterplots or parallel coordinates-where adjacency and containment criteria are undefined.

Coupled Zooming and Drilling

Zooming and panning in a visualization can be interpreted as the shifting focus of attention of the viewer. This information can be utilized for also controlling the level of detail of the visualization. In other words, the coupled zooming and drilling operation ensures that zooming into a specific part of a visualization will cause the rendering to traverse deeper into the aggregate hierarchy, yielding more detail (Figure 7). Zooming out will have the opposite effect. Another, perhaps more general, term for coupled zooming and drilling is semantic zooming [START_REF] Perlin | Pad: An alternative approach to the computer interface[END_REF], where the graphical representation dynamically depends on the geometrical properties of the view through which the user is looking at the data. Our use of the term is similar, yet explicitly refers to parameters of the underlying hierarchical visualization.

Coupled zooming and drilling is typically implemented either using a visual entity budget or an entity size tolerance. For the former case, the user or the system may specify the maximum number of visual entities to display, and will at any given moment traverse deeply enough into the aggregate hierarchy to expend this budget. This means that visually filtering out parts of a visualization by zooming or panning into certain regions will allocate more detail to this part. For the latter case, the user or the system maintains a size tolerance for visual entities, and traverses deeper into the tree (i.e. adds more detail) until each visual entity is within this tolerance. Again, this causes geometric zoom and pan to reveal more or less of the details of the aggregate hierarchy.

VISUALIZATION EXAMPLES

Given the above model of hierarchical visual aggregation, we now discuss a number of existing visual representations and see how we can implement hierarchical aggregation to turn them into multiscale structures that are more scalable for massive datasets. Table 1 shows a summary of visual aggregation strategies for the different information visualization techniques discussed here.

Scatterplots

Scatterplots [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF][START_REF] Utts | Seeing Through Statistics[END_REF] visualize multidimensional data by mapping data cases to graphical points in a two-or three-dimensional Cartesian space defined by two or three orthogonal axes. The position of each point representing a data case depends on the data dimension assigned to each axis. Visualization tools supporting scatterplots, such as Xmd-vTool [START_REF] Ward | XmdvTool: Integrating multiple methods for visualizing multivariate data[END_REF], Spotfire, and GGobi [START_REF] Swayne | GGobi: evolving from XGobi into an extensible framework for interactive data visualization[END_REF], typically allow additional data dimensions to be mapped onto graphical attributes such as the size, color, and shape of the points. Because of their relative simplicity, familiarity with users, and high visual clarity, scatterplots are part of the standard vocabulary of data graphics.

Scatterplots are overlapping visualizations, and rendering a large dataset (or even a dataset that is locally dense) will cause a lot of item overlap in the output, making estimation of effects difficult. Fekete and Plaisant [START_REF] Fekete | Interactive information visualization of a million items[END_REF], while not focusing on aggregation per se, present a scatterplot implementation capable of visualizing a million separate items. Their examples clearly show the overlap problem (they even measure the amount of overlap), and they discuss methods involving transparency, stereovision, and interaction to reduce its impact.

As outlined in Table 1, the main visual aggregations for scatterplots involve hierarchical clustering of data points into points, boxes, hulls, and blobs. Point aggregates show only the average for each cluster, and could be seen as a sampling operation [START_REF] Dix | By chance -enhancing interaction with large data sets through statistical sampling[END_REF]. Originally introduced by Yang et al. [START_REF] Yang | Interactive hierarchical displays: a general framework for visualization and exploration of large multivariate data sets[END_REF], boxes are axis-aligned 2D or 3D bounding boxes that give an indication of the minimum and maximum values for the displayed dimensions (Figure 1(b)). They can be augmented to show averages as points or using opacity where the center point of the cluster is fully opaque and the extrema are fully transparent. Wills [START_REF] Wills | An interactive view for hierarchical clustering[END_REF] present a scatterplot-based aggregation method using recursive subdivision of space with boxes.

Hulls are variations on boxes in that they show the extents of the displayed dimensions, but using 2D or 3D convex hulls instead of axisaligned bounding boxes as a tighter visual metric (Figure 1(c)). Just like for bounding boxes, center points or opacity can be used to indicate the cluster average (Figure 8). Bivariate boxplots [START_REF] Wilkinson | The Grammar of Graphics[END_REF] and their simplification, bagplots [START_REF] Rousseeuw | The bagplot: A bivariate boxplot[END_REF], are statistical versions of this technique where concentric hulls are constructed to contain quartiles of the data.

Taking extent refinement even further, the blobs technique proposed by Heine and Scheuermann [START_REF] Heine | Manual clustering refinement using interaction with blobs[END_REF] provide implicit surfaces for conveying and interacting with fine-grained clustering, and can be employed for scatterplot diagrams. However, the authors point out the problem of color blending for overlapping blobs, a problem that generalizes also to boxes and hulls. The weaving approach proposed by Hagh-Shenas et al. [START_REF] Hagh-Shenas | Weaving versus blending: a quantitative assessment of the information carrying capacities of two alternative methods for conveying multivariate data with color[END_REF]

Parallel Coordinates and Starplots

As opposed to the orthographic axes of scatterplots, parallel coordinates [START_REF] Inselberg | The plane with parallel coordinates[END_REF] stack the dimension axes of a multivariate dataset in parallel and visualize items in the dataset as polylines that connect the item's value for each dimension. Starplots [START_REF] Siegel | The surgical implication of physiologic patterns in myocardial infarction shock[END_REF] extend parallel coordinates by arranging the axes in a polar instead of a linear coordinate space, turning the open polylines representing data items into closed ones.

The simplest approach to visualize aggregated parallel coordinates is to just use polylines as visual aggregates for the average of the aggregated data items. van Wijk and van Selow [START_REF] Van Wijk | Cluster and calendar based visualization of time series data[END_REF] describe the use of this representation for hierarchically clustered time-series data. However, the information conveyed through line aggregates is low (only the average value). Also, the line aggregates have no visual affordance that indicates that they are actually aggregates of underlying data items.

To address this problem, Fua et al. [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF], and later Yang et al. [START_REF] Yang | Interactive hierarchical displays: a general framework for visualization and exploration of large multivariate data sets[END_REF], describe a hierarchical visual aggregation approach for parallel coordinate diagrams based on bands that aggregate several polylines (visual data items) into a single band (visual aggregates) as wide as the extrema of the underlying data. This is an n-dimensional generalization of scatterplot boxes and hulls in 2D space. Bands can also convey the average value using opacity just like scatterplot hulls and boxes. See Figure 9 for examples of how to apply hierarchical aggregation to a standard parallel coordinate diagram.

Both lines and bands can be trivially extended to starglyph diagrams [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF][START_REF] Yang | Interactive hierarchical displays: a general framework for visualization and exploration of large multivariate data sets[END_REF] (Figure 10). Recent work on starglyph diagrams introduced the notion of color histograms [START_REF] Elmqvist | DataMeadow: A visual canvas for analysis of large-scale multivariate data[END_REF][START_REF] Elmqvist | DataMeadow: a visual canvas for analysis of large-scale multivariate data[END_REF] showing the data distribution on the surface of the opacity bands (Figure 11). This method could also be employed also for standard parallel coordinate diagrams; Andrienko and Andrienko [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF] show approaches to displaying quartiles and distributions in parallel coordinates using bands and beads, respectively.

Along similar lines, the parallel sets [START_REF] Bendix | Parallel sets: A visual analysis of categorical data[END_REF] technique extends parallel coordinate displays with frequency-based visualizations of categorical data (Figure 12). Sifer [START_REF] Sifer | User interfaces for the exploration of hierarchical multidimensional data[END_REF] develops the idea further by removing the bands connecting data categories and relying merely on color for identification. However, these approaches do not maintain an aggregate hierarchy and are thus not true hierarchical visualization techniques.

Tree Visualizations

When the data structure is a tree, it is generally used as its own aggregation hierarchy. For this reason, we discuss all tree visualizations together in one section. Using the tree structure itself as the aggregation hierarchy is problematic when the tree is unbalanced or when it is either very deep, such as phylogenetic trees, or very wide, such as the Java SDK class hierarchy. In this case, the aggregation hierarchy typically merges or splits some of the original tree nodes but remains congruent with the original tree structure.

Treemaps [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF] visualize tree structures through enclosure using a space-filling layout algorithm based on recursive subdivision of space. The enclosure feature of treemap nodes conveys the extents of underlying nodes in the hierarchy. Furthermore, the surface of an internal tree node serving as a visual aggregate could conceivably be used to show additional information about the node's children. However, because the size of visual entities depend on a specific data attribute, some branches of a tree may disappear (i.e. be allocated display size less than a pixel) [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF], a problem addressed by context treemaps [START_REF] Csallner | FundExplorer: Supporting the diversification of mutual fund portfolios using context treemaps[END_REF] that allocate space even to zero-sized nodes.

Fekete and Plaisant [START_REF] Fekete | Interactive information visualization of a million items[END_REF] give a number of technical solutions for visualizing treemaps on the order of 10 6 items, cutting off rendering for data items that are smaller than one pixel in size.

The zoomable treemaps [START_REF] Blanch | Browsing zoomable treemaps: Structureaware multi-scale navigation techniques[END_REF] introduced by Blanch and Lecolinet combine many of the interaction techniques described in this article with the use of treemaps as a multiscale space for navigation. Their work is instructive in how to extend an existing visualization technique with support for aggregation and navigation in the aggregate hierarchy.

SpaceTrees [START_REF] Plaisant | SpaceTree: Supporting exploration in large node link tree, design evolution and empirical evaluation[END_REF] use standard node-link representations of trees, but support interactive expansion and contraction of tree branches as well as screen-optimized dynamic layout of nodes and automatic camera movement to fit the current display. The technique supports many of the general interaction techniques for hierarchical aggregation described in this article, including local aggregation control, roll-up, and drill-down. Visual aggregates of unexpanded branches are shown using thumbnails that indicate the underlying node topology, or as simple triangle glyphs that show the count and depth of the contracted subtree. Degree-of-Interest trees [START_REF] Card | Degree-of-interest trees: A component of an attention-reactive user interface[END_REF] provide a focus+context [START_REF] Furnas | Generalized fisheye views[END_REF] view of node-link tree representations that are optimized for the screen. As with SpaceTrees, DOITrees define several different visual representations for aggregated subtrees, including elided and glyph representations of their node count and depth.

Node-Link Diagrams

Node-link diagrams are perhaps the most straightforward graph visualizations, drawing a graph as a collection of visual nodes arranged on a 2D or 3D visual substrate using some graph layout algorithm [START_REF] Dibattista | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF] and connected using visual links. However, large numbers of edges or nodes may cause a highly congested visualization despite the use of efficient layout algorithms, prompting the need for hierarchical aggregation [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF], either on edges, nodes, or both.

For node-link diagrams (as opposed to matrix visualizations, see below), edge aggregation is the least common of these approaches and only a few techniques take this route. Hierarchical edge bundles [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF] group links together into thick bundles, akin to how electrical or network wires are tied together to avoid excessive tangling. However, despite its name, this is not strictly a hierarchical visualization technique because the aggregation is performed in visual space using implicit curves and not in data space.

As for node aggregation, there are essentially two approaches to conducting hierarchical aggregation on graphs visualized using node-link diagrams: top-down or bottom-up. In the bottom-up approach, a layout is computed for the whole graph, and the nodes are then hierarchically grouped using geometrical means [START_REF] Gansner | Topological fisheye views for visualizing large graphs[END_REF]. However, by requiring a complete graph layout prior to aggregation, this approach may not scale well to extremely large graphs.

In the top-down approach, on the other hand, we instead start with a hierarchical aggregation and use this to dynamically compute layout as the user is drilling down into the dataset. This strategy is used by the TugGraph [START_REF] Archambault | Tuggraph: Path-preserving hierarchies for browsing proximity and paths in graphs[END_REF] system. Because this approach does not require an expensive global graph layout but instead amortizes this cost online as the user is exploring, it scales better than bottom-up approaches. It is therefore more promising for future work on aggregating large-scale graphs.

In general, Auber et al. [START_REF] Auber | Multiscale visualization of small world networks[END_REF] show how to use hierarchical node clustering for node-link diagrams to turn a graph into a multiscale structure based on its small-world structure. Their Tulip [START_REF] Auber | Tulip -A huge graph visualization framework[END_REF] system uses metanodes to cluster several nodes into a visual aggregate hierarchy. Metanodes may have a standard node visual representation with the union of all incoming and outgoing edges of the aggregated subnodes, or they may also show simplified contents, such as the clustered small-world network as miniature thumbnails for each node.

Building on the previous work, Archambault [START_REF] Archambault | Feature-Based Graph Visualization[END_REF] presents a featurebased approach to visualizing graphs using node-link diagrams, and discusses a range of graph drawing techniques for this purpose. These techniques are designed to draw hierarchical representations of graphs; some of the proposed techniques support local aggregation control using distinct visual aggregates for metanodes such as nested circles (open) and hexagons (closed). The work also presents many specializations of the general principles introduced in this article that are specific to graphs and node-link diagrams; thus, this is a good example of how to adapt hierarchical aggregation to a specific subdomain.

ASK-GraphView [START_REF] Abello | ASK-GraphView: A large scale graph visualization system[END_REF] combines clustering functionality with navigation in hierarchically aggregated node-link diagrams of large-scale externalized graphs. The system supports interactive expansion and collapse of aggregate branches in an unbalanced fashion, and also manages visual clutter through transparency and masking of edges, similar to the interaction techniques catalogued in this article.

The NodeTrix [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] technique combines node-link diagrams with adjacency matrices for representing communities in social networks. This method utilizes a fixed two-level aggregation where subsets of a graph are clustered and rendered as adjacency matrices connected to other matrices using edge bundles similar to Holten's hierarchical edge bundles [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF]. Because the aggregation is fixed, however, many of the interaction techniques described in Section 3.5 do not make sense for NodeTrix visualizations.

In an extension [START_REF] Elmqvist | CiteWiz: a tool for the visualization of scientific citation networks[END_REF] of the growing polygons [START_REF] Elmqvist | Causality visualization using animated growing polygons[END_REF] dependency visualization, Elmqvist and Tsigas show how to augment the technique with hierarchical subsets that group together nodes in a directed acyclic graph. Their visual aggregate representation shows the cumulative dependencies for each subset, and additionally adds a drop-shadow to indicate that the subsets can be expanded (Figure 13).

Fig. 13. Visual aggregate representation for the hierarchical growing polygons visualization technique [START_REF] Elmqvist | CiteWiz: a tool for the visualization of scientific citation networks[END_REF]. Dependencies for the aggregate is the sum of its children's dependencies and the shadows give a visual affordance that the aggregates can be expanded.

Finally, pivot graphs [START_REF] Wattenberg | Visual exploration of multivariate graphs[END_REF] exploit data cube aggregation [START_REF] Stolte | Multiscale visualization using data cubes[END_REF] to roll-up nodes into metanodes based on attribute values for categorical data. A specialization of hierarchical aggregation, this allows for the creation of simplified node-link graphs showing primarily the counts of aggregated nodes and edges. However, because the aggregation again is not hierarchical in nature, the interaction techniques described in this article do not apply to pivot graphs.

Adjacency Matrices

Instead of explicitly drawing nodes and edges as graphical entries laid out on a visual substrate, adjacency matrices arrange nodes along the rows and columns of a matrix and represent edges between nodes as cells in the contents of the matrix. Adjacency matrices have been shown to be more efficient than node-link diagrams for large and/or dense graphs [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis[END_REF], and are thus often employed for visualizing large graphs, either alone or in tandem [START_REF] Henry | MatrixExplorer: a dual-representation system to explore social networks[END_REF] with node-link diagrams.

The NodeTrix [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] technique mentioned in the previous section is an example of an aggregated hybrid between node-link and matrix representations. However, as noted above, the technique is not a true aggregated visualization due to its fixed aggregation structure.

The Matrix Zoom [START_REF] Abello | Matrix Zoom: A visual interface to semiexternal graphs[END_REF] system, on the other hand, takes edge aggregation to its extreme by displaying large-scale graphs as a hierarchy of adjacency matrices given a predefined clustering hierarchy. Matrix Zoom uses animated transitions between levels in the aggregate hierarchy instead of supporting continuous zoom and pan interactions.

Similarly, the Zoomable Adjacency Matrix Explorer (ZAME) [START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF] defines a pyramid of recursive edge merging where each level is half the dimension of the level below. Hence, each visual edge aggregate clusters four visual aggregates in the level below (Figure 14). This way, ZAME is able to visualize very large graphs on the order of 10 6 nodes and edges (Figure 15). Instead of fixed animations, like Matrix Zoom, the system implements many of the interaction techniques outlined in Section 3.5 of this article such as zoom and pan, drill-down/roll-up, and coupled zoom and drill. In addition, the system also provides a rich set of visual representations for edge aggregates (Figure 16) drawn using small programs (shaders) running on the graphics hardware.

n/16 n/4 n/2 ... n h = ceil(log2(n))
Fig. 14. Pyramid aggregation hierarchy for the ZAME [START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF] system. Each aggregate node represents four nodes in the level below.

Geometric Visualizations

Two-dimensional or three-dimensional geometric visualizations for scientific data are routinely turned into aggregated visualizations using spatial aggregation techniques such as quadtrees, octrees, and other spatial hierarchies (Figure 20). The same interaction techniques as for other aggregated visualizations can be used for these visualization techniques, allowing for geometric zooming, drilling down, and rolling up the data. Coupled zooming and drilling is often used to show more details in regions the user is zooming into. . ZAME [START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF] visualizing a protein-protein interaction dataset of 100,000 nodes and 1,000,000 edges. Inset shows a magnified view of step histogram edge aggregates in the matrix. The standard visual representation of aggregates for geometric visualizations is to simply use the average color shade of the children to represent an aggregate. Andrienko and Andrienko [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF] show how to aggregate geospatial data while retaining metadata, such as geographical outlines and labels (like the continent outlines in Figure 20).

While geometric visualization is a very large topic, most geometric visualization techniques fall within the realm of scientific visualization. Therefore, geometric visualization are beyond the scope of this article where we concern ourselves mainly with information visualization.

DESIGN GUIDELINES

Having formalized a model of hierarchical aggregation for visualization and surveyed existing examples for supporting aggregation in visualization techniques, we now derive a set of general guidelines for designing and implementing such techniques: G1 Entity budget. Maintain an entity budget;

G2 Visual summary. Aggregates should convey information about underlying data;

G3 Visual simplicity. Aggregates should be clean and simple; G4 Discriminability. Aggregates should be distinguishable from data items; G5 Fidelity. Beware that abstractions may lie; and G6 Interpretability. Aggregate items only so much so that the aggregation is still correctly interpretable within the visual mapping.

We describe each of these guidelines in greater depth below.

Entity Budget (G1)

Principle: Maintain a visual entity budget when rendering hierarchical aggregated visualizations.

Discussion: Aggregated visualizations automatically support the use of a budget of the number of visual entities to draw. If for no other reason than technical, it makes sense to cut off rendering for entities smaller than a pixel. In addition, it makes even more sense to control the amount of data rendered on the screen to avoid visually overloading the viewer.

The added benefit of a visual item budget is that it limits time spent on rendering and guarantees a lower bound on the framerate.

Visual Summary (G2)

Principle: Visual aggregates should convey information about the underlying data.

Discussion: We should design our visual aggregates to convey information about the underlying data that is currently not visible. This is one of the most basic features of a hierarchically aggregated visualization: the viewer can gain a reasonably detailed overview of a dataset while not being overloaded by the full data.

In some cases, it may even be useful for visual summary reasons to adopt an adaptive rendering scheme as described in Section 3.4 so that areas of the visualization with interesting features are automatically rendered at higher detail level than those with less variance.

Visual Simplicity (G3)

Principle: Design visual aggregates to have a clean and simple visual appearance.

Discussion: The purpose of aggregated visualizations is to reduce clutter in order to improve overview. Remember that even visual aggregates may be rendered in large quantities, so choosing a visual representation that is too complex or attempts to convey too much information may cause clutter in the visualization all over again. The simplest possible choice of visual representation for the visual aggregate may often be the one used for visual data items. However, as argued by G4, this is often a bad idea, so a more complex (or at least different) representation may be necessary.

Discriminability (G4)

Principle: Design visual aggregates to be easily distinguishable from visual data items.

Discussion: Visual aggregates and visual data items must be easy to differentiate in order to not convey the wrong information to the viewer. While using the same visual representation for both aggregates as for items is often easiest, it may give the viewer the wrong idea about the data.

For example, the aggregate of two points in a scatterplot might be a single point, or the aggregate of two polylines in a parallel coordinate display might be a single polyline on their average [START_REF] Van Wijk | Cluster and calendar based visualization of time series data[END_REF]. A better choice is to introduce a novel representation for the visual aggregate, or to decorate the aggregate with some extra graphical feature, like the shadows for the growing polygons technique [START_REF] Elmqvist | CiteWiz: a tool for the visualization of scientific citation networks[END_REF] (Figure 13).

Fidelity (G5)

Principle: Counteract fidelity problems in visual aggregates. Discussion: Data abstraction operations simplify datasets, but inherent in this process is also a loss of fidelity-the visualization may, in effect, lie about the size of the effect [START_REF] Rogowitz | How not to lie with visualization[END_REF][START_REF] Tufte | The Visual Display of Quantitative Information[END_REF]. This should be made clear to viewers using a visualization, either explicitly as done by Cui et al. [START_REF] Cui | Measuring data abstraction quality in multiresolution visualizations[END_REF], or by indications in the visual aggregates (i.e. deliberately choosing rough or imprecise visual indications of the aggregated data).

The use of averaging for data aggregation can be particularly problematic; Hans Rosling's TED 2006 talk about global health highlights how misleading averages can be when aggregating groups of countries together. Or, as Andrienko and Andrienko remark, "the mean surface temperature on the Moon may seem quite comfortable, but the actual temperature ranges from -230 • C to +130 • C, and this should be taken into account in designing clothes for astronauts." [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF] Fortunately, the very tools provided by this article-interactive aggregation control-are exactly what is needed to counteract this problem. Drilling down into the dataset, if only a few levels down, will invariably uncover inconsistencies compared to higher-level aggregations.

Interpretability (G6)

Principle: Aggregate items only so much so that the aggregation is still correctly interpretable within the visual mapping.

Discussion: Related to guideline G5, this guideline reinforces the basic message of this article: aggregates convey meaning to the viewer, and if an aggregate is degenerate, it will cause the viewer to easily become misinformed. Items should not be aggregated merely for the sake of reducing visual complexity, but the aggregation should also be interpretable to the viewer in visual space.

For example, aggregates in a space-filling visualization based on containment, such as treemaps [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF] or pivot graphs [START_REF] Wattenberg | Visual exploration of multivariate graphs[END_REF], carry high interpretability. However, an overlapping visualization such as a scatterplot, for example, will have low interpretability if the items are aggregated using dimensions not mapped to the visual attributes (i.e., the vertical and horizontal axes for a 2D scatterplot). Also relevant in the interpretability discussion is the fact that visual aggregates should be designed so that they communicate to the viewer that there is more to see by expanding aggregated nodes (this goes hand in hand with guideline G4, which states that visual aggregates and visual data items should be distinguishable from each other).

EXAMPLES

In this section, we illustrate our model and design guidelines for hierarchical aggregation by studying how we can apply it to two different visualizations: a treemap [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF] and a line graph.

Aggregated Treemaps

In this example, we study how to augment an existing zoomable treemap visualization [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF][START_REF] Blanch | Browsing zoomable treemaps: Structureaware multi-scale navigation techniques[END_REF] with hierarchical aggregation support. In this way, we can turn the visualization into a multiscale structure suitable for supporting both overview as well as detail tasks.

We start our design from a basic slice-and-dice treemap [START_REF] Shneiderman | Tree visualization with tree-maps: A 2-D space-filling approach[END_REF] implemented in Piccolo [START_REF] Bederson | Toolkit design for interactive structured graphics[END_REF] (Figure 17). The visualization already supports zoom and pan (Section 3.5.1) in geometric space, as well as flipping (Section 3.5.4) for visiting sibling nodes. However, the hierarchies that we want to represent using this visualization, such as a filesystem directory structure, may become arbitrarily large (easily more than 1 million entities [START_REF] Fekete | Interactive information visualization of a million items[END_REF]). This immediately gives rise to the two basic problems of large-scale datasets, performance and perception:

• Performance: Rendering performance will suffer for very large hierarchies.

• Perception: It is difficult, if not impossible, to get an overview of the dataset due to the large number of visual entities.

To help remedy this situation, we can apply design guideline G1 (entity budget) to begin introducing hierarchical aggregation to the visualization. In this case, we can utilize the tree structure itself as the aggregation hierarchy, saving us some work. Furthermore, G1 tells us that we can address both of the above problems by maintaining a visual entity budget and not propagate deeper into the aggregation hierarchy than necessary. In particular, there is clearly no need to draw any nodes that are smaller than a pixel for a given level of zoom. For this situation, we replace the visual representation of the aggregate and its children with a checkered pattern to communicate to the viewers that there is additional underlying data to be seen if they zoom in (G2). While this pattern may conflict with G3 (visual simplicity), it is better than the alternative, i.e., to attempt to draw all of the nodes, even though they are smaller than a pixel each. Furthermore, we believe that the checkered pattern still gives a clear visual indication that there is more to see in the checkered area.

However, while our entity budget solves our performance problems by capping the amount of entities to draw at any time, it has not fully solved the perception problem because this budget may still be larger than the information processing capacity of the viewer. To better support overview, we introduce local aggregation control (Section 3.5.3), where the user can selectively expand and collapse branches by rolling the mouse wheel or clicking (left-click for expand and right-click for collapse) individual entities on the display. This gives the user direct control of which detail level to view the hierarchy, while simultaneously supporting drill-down and roll-up operations (Section 3.5.2). According to guideline G4, we must now make sure that aggregates and items can be easily distinguished. We achieve this by coloring aggregates blue, while items remain green. This also gives a straightforward indication that there is more information to be gleaned if the user simply expands a specific aggregate. Other possibilities to communicate this may have been to use a special border for the aggregate nodes, or to add a drop shadow or a "stack" graphic to the node (like for the processes in the growing polygons [START_REF] Elmqvist | Causality visualization using animated growing polygons[END_REF] technique).

We can now make the observation that by cutting down on the visual complexity as described above, we have also reduced the amount of information conveyed through the visualization. Guideline G2 tells us that aggregates should communicate information about the underlying (aggregated) data, while guideline G5 admonishes us to be conservative in doing so, lest we end up with an even more visually complex display than before. Our solution is to introduce a family of simple glyphs (similar to the glyphs in the ZAME [START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF] system) drawn in the corner of each treemap node that show various metrics of the contained subtree. In particular, we use a small bar histogram to show the distribution of file sizes in a directory structure (Figure 18). When designing the glyphs, we must also be mindful of guideline G5, which tells us to indicate the decreased fidelity of the glyph representations; interactive aggregation control also helps in this.

However, at this point, we note that the rectilinear appearance of a histogram rendered as a bar chart may be easily confused with the rectilinear visual representation of the treemap. This conflicts with guideline G4, which states that visual aggregates should be easily distinguishable, as well as to some extent G3, which argues for a clean visual appearance of visual aggregates. To avoid this conflict, we must find a visual appearance for the histogram glyph that is easily distinguishable from the treemap representation. One option may be to round the edges of the bar chart glyph, but this may not be sufficient for accurate disambiguation. Instead, we choose to add a new type of glyph based on pie charts to make the distinction perfectly clear.

Another important point to consider is guideline G6, which states that taking the aggregation too far may cause misinterpretation. Fortunately, treemaps generally have high interpretability due to their parent-child layout. However, for our aggregated treemap, initializing the visualization to show only the root of the tree as a single visual aggregate may cause the viewer to misunderstand the data, or even think that there is nothing more to see in the visualization. A simple solution is to expand the first few levels of the tree upon initialization, as well as to explicitly show that there is underlying data to explore, for example by giving the number of children in a tooltip or label.

Figure 19 shows the final redesigned version of our treemap visualization, now with support for hierarchical aggregation. The visualization has been implemented in Java using the Piccolo [START_REF] Bederson | Toolkit design for interactive structured graphics[END_REF] toolkit, and can be executed using a Web browser from the following URL:

https://engineering.purdue.edu/ elm/projects/aggtreemap/

Aggregated Line Graphs

Basic line graphs are a ubiquituous form of data graphics [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF] used to show all manners of data ranging from sequences of sensor readings such as seismographic, biological, and scientific data, as well as general data such as bandwidth usage, stock market data, and popularity ratings, to name a few. Recent work by Byron and Wattenberg [START_REF] Byron | Stacked graphs -geometry & aesthetics[END_REF] also studied aesthetics and layout techniques for stacked graphs, a specialization of line graphs.

Without going into the detail of the previous example for aggregated treemaps, adding hierarchical aggregation to a line graph can be done in essentially two ways: either by (1) aggregating the dimensional axes (X or Y), or by [START_REF] Abello | ASK-GraphView: A large scale graph visualization system[END_REF] aggregating multiple data series shown in the same graph. The approach taken will result in radically different designs.

For the first approach, aggregating the axes, Andrienko and Andrienko [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF] show how to aggregate dimensions into higher-level intervals-e.g., aggregating 60 measurements at one-second intervals into a single measurement for a one-minute interval. A suitable visual aggregate (obeying G2, G3, and G4) could be to show the envelope (i.e., the extents) for each aggregated unit, as well as additional data such as average, median, or even distribution. By controlling the interval size, we can easily maintain a visual entity budget (G1).

For the other approach, van Wijk and van Seelow [START_REF] Van Wijk | Cluster and calendar based visualization of time series data[END_REF] use hierarchical clustering-thus supporting an entity budget (G1)-to combine multiple time series into averages of the underlying data (G2) and then represent them as normal line graphs in the display. However, while this is certainly simple (G3), the visual aggregates are not distinguishable from the visual items (violating G4). Also, care must be taken to control the level of clustering so that the resulting line graph does not misrepresent the underlying data (G6). A perhaps better approach would be to adapt the opacity bands [START_REF] Fua | Hierarchical parallel coordinates for exploration of large datasets[END_REF][START_REF] Yang | Interactive hierarchical displays: a general framework for visualization and exploration of large multivariate data sets[END_REF] representation to show the extents and averages of several aggregated data series.

CONCLUSIONS AND FUTURE WORK

Our ambition with this article has been to present a model for hierarchical aggregation in information visualization for the purpose of improving overview and scalability of large-scale visualization. While the focus of our work is primarily on supporting the limited perceptual capabilities of the human viewer, many of these techniques will also come in useful for overcoming the technical challenges of rendering massive datasets. We have surveyed a set of standard visualization techniques and seen how they can be extended with hierarchical aggregation functionality. We have also described a set of general interaction techniques for manipulating aggregated visualizations. From this work, we have been able to formulate a set of common design guidelines for building new aggregated visualization techniques as well as extending existing ones with hierarchical aggregation.

Our future work will include refining the model further and deriving new interaction techniques that are common to this whole class of aggregated visualizations. We are also interested in experimentally examining the trade-off between simplification and accuracy that is inherent in all data abstraction models. Furthermore, coupling geometric zoom and level-of-detail expands the model of space-scale diagrams by providing an additional parameter: the granularity/density of the visualized items, an aspect that we want to study further. Finally, this article so far only discussed tree-shaped hierarchical aggregation schemes-a more powerful concept to explore in the future would be to use DAGs for hierarchical aggregation of certain data structures.

  (a) 2D scatterplot visualization. (b) 2D bounding box aggregation.(c) 2D convex hull aggregation.

Fig. 1 .

 1 Fig. 1. Hierarchical visual aggregation of a 2D scatterplot visualization. Note that scatterplots are overlapping, so occlusion can occur.

Fig. 2 .

 2 Fig. 2. Rendering traversal types for hierarchical aggregated visualizations. Arrows indicate the current aggregation height. White nodes are rendered to the screen while gray nodes are omitted from rendering.

Fig. 3 .

 3 Fig. 3. Zoom and pan interaction. (a) Pure pan. (b) Zoom out to show two items. (c) Combined zoom in and pan.

Fig. 4 .

 4 Fig. 4. Drill-down and roll-up interaction. (a) Drill-down from level 1 to level 2. (b) Roll-up from level 2 to level 1.

Fig. 5 .

 5 Fig. 5. Local aggregation control. (a) Unbalanced drill-down.

Fig. 6 .

 6 Fig. 6. Flipping interaction. (a) Flip between adjacent siblings.

Fig. 7 .

 7 Fig. 7. Coupled zoom and drill interaction. (a) Drill-down and zoom in. (b) Roll-up and zoom out.

  (a) Parallel coordinate visualization. (b) Opacity band aggregation (above-traversal). (c) Opacity band aggregation (below-traversal).

Fig. 9 .

 9 Fig. 9. Parallel coordinate visualization of an 8-dimensional dataset with opacity band [34] visual aggregations. Transparency is used to indicate the extrema and the averages for each visual cluster band.

Fig. 10 .

 10 Fig. 10. Starglyph visualization of an 8-dimensional dataset with opacity band [34] visual aggregations. Transparency indicates the extents and the averages for each opacity band.

Fig. 8 .

 8 Fig. 8. Convex hull visual aggregation of a 2D scatterplot. Transparency is used to indicate the centers of each hull aggregate.

Fig. 11 .

 11 Fig. 11. Color histogram representation of a multidimensional university student dataset in a starglyph visualization from the DataMeadow [29, 30]. Brightness indicates high density.

Fig. 12 .

 12 Fig. 12. Parallel set visualization of categorical customer data [11]. Histograms for each axis show the distribution of data points.

Fig. 15

 15 Fig. 15. ZAME[START_REF] Elmqvist | ZAME: Interactive large-scale graph visualization[END_REF] visualizing a protein-protein interaction dataset of 100,000 nodes and 1,000,000 edges. Inset shows a magnified view of step histogram edge aggregates in the matrix.

Fig. 16 .

 16 Fig. 16. Visual edge aggregate representations for ZAME [28] (average color shade, average, min/max curve, min/max range, min/max tribox, Tukey box, smooth histogram, step histogram).

Fig. 17 .

 17 Fig. 17. Slice-and-dice treemap visualization showing a typical Cygwin distribution for Windows (648 directories, 6552 files, 181 MB).

Fig. 18 .

 18 Fig. 18. Aggregate treemap visualization of the above file structure. Directories (aggregates) are blue, files (items) are green. Histogram glyphs show the file size distribution for each unexpanded directory, and nodes too small to render are drawn using a checkered pattern.

Fig. 19 .

 19 Fig. 19. Aggregate treemap of the cygwin file distribution. Pie chart glyphs are drawn for file size distribution to avoid the visual complexity of bar chart histogram glyphs.

Niklas

  Elmqvist is an assistant professor in the School of Electrical and Computer Engineering at Purdue University in West Lafayette, IN, USA. Having joined Purdue in fall 2008, he was previously a Microsoft Research postdoctoral researcher in the AVIZ team of IN-RIA Saclay -Île-de-France located at Université Paris-Sud in Paris, France. He received his Ph.D. in December 2006 from the Department of Computer Science and Engineering at Chalmers University of Technology in Göteborg, Sweden. His research specialization is in information visualization, human-computer interaction, and visual analytics. He is a member of the IEEE and the IEEE Computer Society. Jean-Daniel Fekete is a Senior Research Scientist (DR2) at INRIA Saclay -Île-de-France, one of the leading French national research centers, in Orsay, south of Paris. He leads the AVIZ team since 2007, which focuses on data analysis and visualization research. The AVIZ team is located in and collaborates with the Computer Science Department (LRI) at Université Paris-Sud. AVIZ studies analysis and visualization of large datasets, combining machine learning approaches with information visualization and multiscale interaction techniques to help analysts explore and understand massive data. Jean-Daniel's research topics include network visualization, evaluation of information visualization systems, and toolkits for user interfaces and information visualization. His research is applied in several fields such as biology, history, sociology, digital libraries, and business intelligence. He is a member of the IEEE.

Table 1 .

 1 Visual aggregation strategies for a set of basic information visualization techniques (O/L = overlapping, S/F = space-filling).

	starts with treating each item as its

ACKNOWLEDGMENT

This work was supported in part by a grant from the joint Microsoft Research/INRIA ReActivity project.