Supporting multifaceted viewing of word clouds with focus+context display

Abstract

Word clouds provide an effective way to visually summarize important keywords from a large collection of text. Despite their increasing popularity, relatively less attention has been paid on developing interactive techniques for flexible word cloud navigation and manipulation. In this article, we present a focus + context display technique to support multifaceted viewing of word clouds. In our algorithm, the sizes of words in a word cloud are first changed to reflect the current importance metric selected by the user and then scaled to balance space utilization and word readability. To remove word overlaps caused by changes of sizes while maintaining the positional dependency modeled by a directed acyclic graph, we propose a force-directed model that also maximizes the utilization of display space. We demonstrate the effectiveness and usefulness of our techniques through case studies using a real-world dataset and evaluate the performance of the constraint-based overlap removal method in achieving stable layouts during importance transformation.

Keywords

Text visualization multi-attribute visualization focus+context visualization tag cloud multivariate data

Introduction

Word clouds have been widely used as a visual communication tool for users to quickly learn important words from a large collection of text. While the display and representation of word clouds^1–4 have been widely studied by information visualization researchers, interaction of word clouds is often relegated to a secondary role. This is because the importance, and hence the size of a word in a word cloud, is typically determined by a fixed criterion. Once the cloud is displayed, the image of the word cloud will remain static. In many real-world applications, however, the importance of a word can change based on the user’s intention in using text. For instance, consider a collection of National Basketball Association (NBA) players as the words in a word cloud. Each player is associated with multiple facets: points, rebounds, assists, steals, blocks, and so on. A word cloud visualization of NBA players allows one to understand the players’ performance based on any one of the above criteria. Frequently, the players need to be analyzed in different aspects and hence the user will use different measures to determine the size of the words in a sequence. In a different scenario, the user may choose to browse the players by the teams that they belong to. The user can choose one or multiple teams to view details on demand, and the importance of the players will change depending on whether they are in the team of interest. To ensure a stable viewing experience as the user moves across a large information space with multiple facets using word clouds, the main issue to address is how to adjust the layout of the word cloud dynamically while preserving the user’s mental map during the transformation of importance, reflected by the size of words. This is important because without preserving a proper context for effective tracking of the words, the user may quickly lose his or her focus and cannot find the relevant words displayed in a totally different layout.

Interaction is an integral part of information visualization.^5,6 Without interaction, a word cloud visualization becomes merely a static image, which significantly limits its use as a fundamental data exploration tool. While some researchers have previously addressed issues related to interactive manipulation of word clouds,^7,8 their works are primarily focused on improving the display of word clouds (such as modifying the color, position, or orientation of a word), and thus, the interaction of word clouds for visual exploration is still an open problem. In this article, we present a focus + context display technique to support multifaceted viewing of word clouds. By multifaceted, we mean the importance of the words can change as the user changes the criterion with which he or she ranks the importance of the words. Focus + context display techniques such as fisheye lens⁹ provide a good balance between the local detail and the global context simultaneously. In this work, focus + context is used to highlight more important words with large font sizes, while preserving the contextual words in the surrounding without affecting the overall readability of the word cloud. The focus words can be selected based on one facet chosen by the user, such as points per game in the NBA players example, or explicitly selected by the user by a mouseover to a word followed by semantic zooming,¹⁰ that is, selecting words of interest as the foci, with additional words introduced to augment the information presented by the word cloud.

In our algorithm, non-focus words are displayed as the context to facilitate effective navigation and tracking. The sizes of the words after importance transformation are scaled to balance space utilization and word readability. To remove the overlaps caused by changes of word sizes while maintaining positional dependencies, we propose a force-directed model to solve the constraints specified by a directed acyclic graph (DAG) to adjust the layout and maximize the utilization of display space. We demonstrate the effectiveness and usefulness of our techniques through case studies on NBA player data and quantitatively evaluate the values of the constraint-based overlap removal approach compared with a competing method. The major contributions of this work are as follows:

A focus + context display technique to support multifaceted viewing and navigating of word clouds. It preserves the user’s mental map while the importance of words is changed when the user browses through the information with multiple facets. Our technique also supports semantic zooming by introducing additional words that are relevant to the selected words.

An overlap removal method that preserves the positional dependencies among the words, while maximizing the utilization of display space. Based on a dependency graph that models positional dependencies among the words, a force-directed model is employed to solve the constraint-based overlap removal problem.

Related work

Originating from social tagging on the Internet, word clouds have been used to display keywords from text collections. Many Eyes,¹¹ Wordle,⁷ and other online visualization tools enable users to create their own word clouds from text collections. Lohmann et al.¹² showed that no single best layout can be suitable for all word clouds. Considerable research has been done in word cloud layout adjustment. Tag Maps¹³ placed tags on maps to summarize topics of photos in different places. Kaser and Lemire¹⁴ used Electronic Design Automation algorithms to pack layout for HTML-based word clouds. Seifert et al.¹⁵ proposed a region clipping method for placing words in a better shape. Wordle⁷ allowed flexible orientation of word clouds in a compact layout, and Mani-Wordle⁸ supported user control over the layout of a word cloud. Collins et al.¹ introduced parallel tag clouds by integrating both parallel coordinates and tag clouds. Cui et al.² proposed coherent layouts for dynamic word clouds. Wu et al.¹⁶ created semantic-preserving word clouds by leveraging tailored seam carving. ProjCloud⁴ achieved a semantically consistent layout from a set of documents. Besides, there have been studies to evaluate display utility in a word cloud. Rivadeneira et al.¹⁷ found that larger words are easier for people to recognize and remember. Halvey and Keane¹⁸ also showed that a larger font size is often important for users to find information quickly and easily.

Focus + context display techniques have been widely used in interactive exploration of large datasets for various information visualization applications, such as tables,¹⁹ trees,^20,21 graphs,²² maps,²³ treemaps,²⁴ metro maps,²⁵ and hybrid visualizations.²⁶ Stoffel et al.²⁷ proposed a focus + context display technique to improve the readability of document thumbnails. ViSizer²⁸ adapted the focus + context technique in resizing visualizations. However, existing focus + context methods are not suitable for word cloud visualization when the sizes of words change dynamically since they can result in either word overlaps or empty spaces among words. Many overlap removal algorithms were discussed and compared by Strobelt et al.,²⁹ but they ignored the boundary constraint and did not consider the issue of space utilization when removing word overlaps. Eppstein et al.³⁰ proposed an optimization approach for matching a layout with overlaps to a grid layout, but it can only deal with nodes of the same bounding areas. In the graph drawing community, constrained optimization is used to create constrained graph layouts. Dwyer³¹ proposed a constraint relaxation scheme to satisfy orientation, circular or non-overlap constraints for large graphs. Dwyer et al.³² also tried to preserve the orthogonal order in graph layouts using a quadratic programming algorithm. Our approach is to satisfy the orthogonal order and space boundary constraint, while removing overlaps of words of varying sizes heuristically.

Multifaceted viewing of word clouds with focus + context display

In this section, we first describe typical usage scenarios for multifaceted viewing of word clouds and then highlight the principles for designing a focus + context display to support multifaceted viewing of word clouds. After that, we describe the algorithms used for creating focus + context display of word clouds.

Usage scenarios

In many visual exploration applications, the importance of a word can change based on the user’s goal when visualizing the text collection. In one scenario, a word can be associated with multiple measures of importance. Each measure describes one facet of the word from the data. Although one can always combine multiple measures to form a single importance, in practice, users may need to examine different facets of the words in a sequence. For instance, when looking at a word cloud of NBA players, one may first want to rank the players based on the points they have scored, and then focus on the minutes they have played on average, and next compare their salaries in the league. In another scenario, different users may show different degrees of interest to the words in the same word cloud, such as the players of different teams in our NBA example. This is common when there are a large number of words in a word cloud, and one is likely to choose and focus on a portion of words with higher interest. Both scenarios require multifaceted viewing of word clouds.

The goal of this work is to support multifaceted viewing of word clouds with focus + context display techniques, which provide a good balance between the local detail and the global context simultaneously. In the first scenario, when switching the focus and context, the importance transformation will change the sizes of all the words in the word cloud to reflect the relative importance of the newly selected facet. In the second scenario, to present more detailed information of the words in focus, semantic zooming¹⁰ is adopted to display additional words that are semantically related to the focus in the nearby locations, while still maintaining a global view of the context. In this way, the user can learn new information related to the words of interest as he or she interacts with the word cloud.

Design principles

To achieve a desired focus + context display of word clouds, we identify the following requirements:

(P1) Transforming the word cloud without geometric distortion. The original geometric shape of words should be preserved as they are the most prominent property to maintain the words’ readability. Therefore, geometric distortion that is commonly used in conventional focus + context techniques should be avoided during the transformation.

(P2) Maximizing the utilization of display space. Because display space is precious, especially for smaller devices, the placement of words should maximize space utilization.

(P3) Maximizing the number of legible words in context. It is necessary to avoid displaying words in context that are too small to be legible after transformation, but in the meanwhile to keep the number of displayed words maximum with consistent relative importance.

(P4) Removing overlaps while preserving spatial proximity. Changing the word sizes is very likely to introduce word overlaps. Spatial coherence should be preserved to maintain the user’s mental map while removing word overlaps.

(P5) Constraining words within the display space. After importance transformation, scaling, and overlap removal, words should always be displayed within the given display space to prevent loss of information.

(P6) Allowing users to switch focus and context smoothly. All changes in the focus + context transformation should be done smoothly to maintain the user’s mental map during transformation.

Space-optimized scaling

Since importance transformation may drastically change the sizes of words, it can result in a word cloud of poor readability (as shown in Figure 1(a)). As discussed in section “Design principles,” a desired focus + context display should maximize the utilization of display space (P2) as well as the number of legible words (P3). While one can uniformly scale the whole word cloud to fit the display space, some words may be still too small to be legible, particularly when many words are very large after scaling, or too many additional words are introduced. To amend this problem, we opt to filter out the less important words in context to make room for the more important words, whose sizes can then be adjusted to make them legible with the additional space. Although the total number of words in context will reduce in the resulting word cloud, the information conveyed in the new word cloud will increase due to an increase in the number of legible words.

Figure 1.

Improving the readability of a word cloud with the space-optimized scaling (SOS) algorithm and our force-directed model. It first identifies and adjusts words in the (a) initial word cloud that are too small with an optimal degree of efficiency e and then removes (b) word overlaps in the word cloud while refining the layout with the positional dependencies and constraints preserved using our force system. During the process, three less important words in (a) are filtered out, resulting in the (c) final word cloud.

To determine the number of words in context to be removed with regard to the available display space G, we define the degree of efficiency e for measuring space utilization

e = \frac{\sum_{i = 1}^{N} B_{i}}{| Γ |}

where B_i is the bounding area of word i, N is the number of words, and $Γ$ is the area of the display space. An ideal word cloud that utilizes exactly the available display space will have e = 1. When e > 1, some words will inevitably fall outside the display boundary after overlap removal, which we consider undesired because these words may have higher importance than the words in view. With this in mind, our goal of space optimization is to maximize e under the constraint of e≤ 1 when transforming the word cloud to a more legible one. To achieve this, we first adjust the sizes of words to make them legible. There are multiple strategies for resizing words. One approach is to scale words uniformly to keep the relative sizes intact

f^{*} = \frac{f_{legible}}{f_{\min}} \times f

where f is the original font size and f^* is the adjusted font size for each word, f_min is the smallest font size in the word cloud, and f_legible is a user-defined legible font size. Namely, words of font size f^*≥f_legible are considered as legible words. We opt to set f_legible = 12 (point) in our experiments. In general, this option can preserve the relative importance of words when resizing a word cloud. We note that users can design their own resizing criteria that might be more suitable to handle special cases in their applications. Clearly, an optimal degree of efficiency e will attain maximal utilization of the available display space. However, in practice, an optimal e is hard to determine since it depends not only on the bounding area of the words but also on the gaps between words of different sizes and in different alignment. To solve the problem, we employ a bisection process to remove the least important words in context until all words are legible with an optimal e and display a maximum number of the more important words. We call it the space-optimized scaling (SOS) algorithm, which is described in Algorithm 1. We first keep the focus words in the display and then select the maximum number of the largest context words (candidate words) that gives e≤ 1 after font size scaling (this can be done by repeatedly including the largest non-candidate context word as a candidate word and checking whether e > 1 after scaling). Next, we perform a binary-search-and-test using our force system (described in section “Force-directed model”) to remove the smallest candidate words until the whole word cloud can fit the display space without overlap.

With the SOS algorithm, we are able to transform a word cloud of poor readability (shown in Figure 1(a)) to a much more effective one (shown in Figure 1(b)), where all words are legible with an optimal e. Our force system (described in section “Force-directed model”) then refines the layout with the positional dependencies and constraints preserved (described in section “Layout constraints”) to create an overlap-free word cloud (shown in Figure 1(c)).

Layout constraints

After importance transformation and SOS, the main issue to address is how to adjust the layout of the word cloud while preserving the user’s mental map. Some words can overlap other words because their sizes are changed or new words are introduced. To remove word overlaps, previously researchers have shown that an orthogonal ordering invariant can be fairly effective in preserving spatial proximity.^29,30 In our case, since the word cloud after transformation and scaling is already dense, preserving the orthogonal order can approximately minimize the total displacement, a time-consuming process if solved using optimization approaches.³⁰ In our algorithm, we consider orthogonal order as one important criterion to reflect the positional dependencies among the words. To develop a better overlap removal algorithm that satisfies the design principles P4 and P5, we analyze the positional dependencies and constraints among the words before the layout adjustment.

Algorithm 1 Space-Optimized Scaling (SOS)
Input: Words of the bounding areas B_i, font size f_i and position p_i (i $\in$ N), the available display space $Γ$ , and a user-defined legible font size f_legible.
Output: An overlap-free legible word cloud with the optimal e.
Rank the words in context by font size in decreasing order, denoted as M_c. Let the set of words in focus be M_f, with f_i≥ f_legible (i $\in$ M_f) after importance transformation. Pick the top \|M_l\| words (M_l $\subseteq$ M_c) and scale the words in M_l $\cup$ M_f such that: min{f_i \| i $\in$ M_f} = f_legible, and adding a word j(j $\in$ M_l) would make e > 1. t₁ = 0 and t₂ = \|M_l\|. while t₂ - t₁ $⩾$ 1 do t = ⌈(t₁+ t₂)/2⌉. Choose and place the top t words in M_l (denoted as M_t) at their original positions, and adjust the positions of the words in M_t $⩾$ M_f via the force-directed model. if the force system converges then t₁ = t. else t₂ = t. end if end while Adjust the positions of the words in M_t $\subseteq$ M_f via the force-directed model.

Positional dependency

To provide a consistent view between the original and the transformed word clouds, the positional dependencies in the orthogonal order should be preserved to produce a visually stable layout. For example, in the word cloud shown in Figure 2(a), the horizontal order of words is WordA → WordB → WordC → WordD → WordE, and the vertical order of words is WordA → WordC → WordE → WordB → WordD. With both horizontal and vertical orders preserved, the resulting layout will be very similar to the original layout and thus have a consistent view when the focal area is changed. We introduce a directed graph, called dependency graph, to model these positional dependencies. A word cloud has two dependency graphs that model the horizontal and vertical positional dependencies separately, denoted as G_x and G_y, respectively. A dependency graph is essentially a DAG as a result of the partial dependency order among the words. Figure 2(b) and (c) depicts the dependency graphs G_x and G_y of the word cloud in Figure 2(a), respectively. The positional dependencies are preserved if and only if the dependency graphs are topologically the same before and after layout adjustment.

Figure 2.

Positional dependency: (a) some words in a word cloud, (b) the dependency graph G_x of (a), and (c) the dependency graph G_y of (a).

Positional constraints

Besides the positional dependencies among the words, the layout also has several other positional constraints to consider during adjustment. One constraint is that one word must not overlap another word since occlusion would dramatically decrease word readability. Another constraint is that words must not go out of the display boundary. Although one can always uniformly resize the entire word cloud to fit in the display boundary when needed, it will reduce the size of every word and may in turn impair the effect of SOS. More importantly, it could also lead to poor utilization of space if the aspect ratio of the bounding box of the resulting word cloud does not match that of the display area. Therefore, a better way to solve this problem is to add a constraint for the words to stay inbound when adjusting the word cloud layout.

Force-directed model

While there exist several overlap removal algorithms for preserving orthogonal order during overlap removal, they do not handle the aforementioned two constraints simultaneously. Heuristic methods such as Rolled-out Wordles²⁹ ignore the boundary constraint, while optimization methods such as point set matching³⁰ can only deal with words with an equal bounding area, and are often time-consuming and thus inappropriate for interactive focus + context word clouds. To satisfy the positional dependencies and constraints among the words, we build a force system to determine the layout of the word cloud. The force system consists of three forces: a dependency force, a boundary force, and a repulsive force.

The dependency force is a spring force that ensures that the positional dependency between two words is preserved; it corresponds to maintaining the topology of the dependency graphs. During the layout adjustment, if an edge in a dependency graph is inverted, the dependency force between the two words takes effect and will adjust their positions either horizontally (corresponding to the dependency graph G_x) or vertically (corresponding to the dependency graph G_y) to recover the original orthogonal order. The horizontal dependency force is formulated as

F_{d}^{(x)} (i, j) = k_{d} | P_{i}^{(x)} - P_{j}^{(x)} |, if (i, j) in G_{x} is inverted

where $k_{d}$ is a weighting coefficient of the dependency force and $P_{i}^{(x)}$ is the x coordinate of word i. The vertical dependency force $F_{d}^{(y)} (i, j)$ is defined similarly to $F_{d}^{(x)} (i, j)$ .

The boundary force is an attractive force that pulls the words that fall outside the display boundary back. Since words are not just points but have finite area, the actual display area $Γ$ for a word must be shrunk by the margin of half the word’s width and height (the dark gray area with dashed boundary in Figure 3(a)), so that the word can be fully displayed as long as its center lies within $Γ$ . The boundary force on word i is formulated as

F_{b} (i) = k_{b} | | P_{i} - Γ (P_{i}) | |, if P_{i} is outside Γ

where $k_{b}$ is a weighting coefficient for the boundary force and $Γ (P_{i})$ denotes the projection of $P_{i}$ to the region $Γ$ —if $P_{i}$ is outside $Γ$ , the projection $Γ (P_{i})$ gives the point on the boundary of $Γ$ that is closest to $P_{i}$ ; otherwise, $Γ (P_{i}) = P_{i}$ . Intuitively, the word outside the display boundary will be dragged along the direction to the nearest point on the boundary by the boundary force.

Figure 3.

Illustration of the force-directed model: (a) the word clouds with regard to the display area $Γ$ , (b) the dependency graph G_x of the leftmost word cloud, and (c) the dependency graph G_y of the leftmost word cloud. Inverted edges are shown in yellow.

The repulsive force prevents a word from being occluded by any other word. It exists between any pair of words if and only if they overlap each other. We decompose a repulsive force into forces in the horizontal and vertical directions. The horizontal repulsive force is formulated as

\begin{matrix} F_{r}^{(x)} (i, j) = k_{r} \\ Δ x, if Δ x > 0 \\ Δ x = \frac{w_{i}}{2} + \frac{w_{j}}{2} - | P_{i}^{(x)} - P_{j}^{(x)} | \end{matrix}

where k_r is a weighting coefficient of the repulsive force, $P_{i}^{(x)}$ is the x coordinate of word i, and $w_{i}$ is the width of the bounding box of word i. The vertical repulsive force $F_{r}^{(y)} (i, j)$ is defined similarly to $F_{r}^{(x)} (i, j)$ —replacing x by y and w by h, where h is the height of the bounding box of the corresponding word. In all the above formulas, a force is set to 0 if the corresponding condition is not satisfied.

Figure 3 illustrates the effect of the three forces. First, the top three figures show an initial layout of a word cloud (Figure 3(a)) with its corresponding dependency graphs G_x (Figure 3(b)) and G_y (Figure 3(c)). Since WordC is occluded by WordA, the repulsive force takes effect between these two words to remove the overlap. Second, the middle three figures show an intermediate layout of the word cloud (after removing the overlap between WordA and WordC) and their corresponding dependency graphs. From the dependency graph G_x, we can see that the edge (D, A) is inverted to (A, D), so the dependency force starts to push WordA and WordD horizontally to recover the original relation. Similarly, the dependency force affects WordA and WordB to move vertically due to the existence of an inverted edge (B, A) in G_y. Besides, since WordC is outside the display area G, the boundary force takes effect to push it back. Third, the bottom three figures show the final layout of the word cloud as well as the corresponding dependency graphs. WordC is inside the display area, and the orthogonal orders of WordA and WordB and WordA and WordD are well preserved—the dependency graphs are topologically the same as those of the initial word cloud.

In our implementation, we employ an iterative process to adjust the positions of words under the three forces. For each word, the order of the forces applied is dependency force, boundary force, and repulsive force. The force system will converge when the words fit in the available display space without overlapping, and also when the dependency graphs have the same topology. To ensure that no word will go out of the display boundary, the boundary force is given a higher weight than the other two forces (namely set k_b > k_d and k_b > k_r). In our experiments, we found k_b = 0.1, k_d = 0.01, and k_r = 0.01 generally allow a quick convergence. We note that if the words have not been scaled appropriately to fit the display area (namely, before the word cloud is refined by the SOS algorithm), it may be difficult for the force system to converge with strict positional dependencies. To alleviate this problem and achieve a faster bisection process, when using the force system to find the optimal degree of efficiency e in the SOS algorithm, we relax the dependency constraint with a smaller weight k_d = 0.001 in step 7 and reset k_d = 0.01 in step 11 of the SOS algorithm to obtain the final layout.

Time complexity

Now, we discuss the time complexity for generating the focus + context display of word clouds with N words. The dependency graphs for an initial word cloud can be generated by sorting the words according to their x and y coordinates, respectively, which can be done in O(NlogN). As a result of the partial order in the dependency graph, for each word, the dependency force can be considered only between it and its parent or child node in the graph, and thus taking O(N) time. The boundary force contributes O(N) time, and the repulsive force can take O(N²) time in the worst case. Therefore, the total time complexity is O(c(N²+N) +NlogN), where c is the total number of iterations in the force-directed adjustment. Although we have not yet specifically optimized the performance such as using a scan-line algorithm to find all the overlaps in O(kN(logN+k)) time,³³ our system can achieve smooth focus + context word cloud transition interactively for several hundreds of words, which is common for most word cloud applications. More details about the actual central processing unit (CPU) running time are shown in section “Quantitative study.”

Evaluation

In this section, we first show the usefulness of our techniques with case studies on NBA player data and then quantitatively evaluate the values of our constraint-based overlap removal method in achieving stable layouts during importance transformation.

Case study

We implemented the focus + context display system using HTML5 and JavaScript. The main benefit of a web-based system is that it is independent of platforms and operating systems, and users can access it from any device with a browser that supports HTML5 without installation and maintenance. An interactive demonstration is presented in a video that accompanies this article.

To demonstrate the effectiveness of the focus + context display of multifaceted word clouds, we used our system to explore the NBA dataset,³⁴ which consists of 442 players from 29 NBA teams during the 2000–2001 season. To generate a semantically clustered word cloud, players of the same team are first placed nearby as a semantic group. Each group is encoded with a color different from its neighboring teams, and the initial size of a word is proportional to the points per game that the corresponding player scored. The coordinates of the words are scaled to fit in the display space and adjusted by our force-directed model to remove word overlaps while preserving positional dependencies and constraints.

In the first case, we explored the players with different importance metrics. Seven metrics are considered: points, rebounds, assists, steals, blocks, games, and minutes, shown in the control panel below the word cloud (see Figure 4). The top 200 players with the highest scores are selected to form an initial word cloud, with their importance measured by the “Points” metric (highlighted in a distinct color in the control panel), as shown in Figure 4(a). Judging by the relative sizes of words, we can observe that some of the scoring leaders are Bryant (Kobe Bryant from Los Angeles Lakers), O’Neal (Shaquille O’Neal from Los Angeles Lakers), McGrady (Tracy McGrady from Orlando Magic), and Iverson (Allen Iverson from Philadelphia 76ers). After selecting the “Assists” metric in the control panel, the importance of each word is transformed to a new value proportional to the number of assists, and the resulting word cloud after scaling and layout adjustment is shown in Figure 4(b). As we can see, although the sizes of words have changed, their relative positions are well maintained—players of the same team are still close to one another, thus preserving the user’s mental map. In addition, the words in the newly selected facet do not overlap one another after changes of sizes and are still legible within the display bounds. From the new focus + context word cloud, we can observe that some of the top supporting players are Kidd (Jason Kidd from Phoenix Suns), Stockton (John Stockton from Utah Jazz), and Bibby (Mike Bibby from Vancouver Grizzlies), which are quite different from the scoring leaders.

Figure 4.

Word clouds of NBA players in the 2000–2001 season: (a) a word cloud of players with the focus on the scoring leaders, ranked by the points they scored, and (b) the same word cloud with the focus on the top supporting players, ranked by the number of assists they made.

In the second case, we navigate the players who belong to different teams with different degrees of interest. Figure 5(a) shows a word cloud of the top 150 players with the highest scores. The focus + context display technique allows one to focus on one or multiple teams, where the players in focus are highlighted with additional players from the same team while the other teams are presented as the context. For instance, from the initial word cloud shown in Figure 5(a), we focused on Mason (Anthony Mason from Miami Heat) and Webber (Chris Webber from Sacramento Kings) simultaneously. Figure 5(b) shows the resulting focus + context display. We can observe that the key players (such as Mason, Jones, Webber, and Stojakovic) from the initial word cloud are magnified as a result of zooming, with their respective teams in focus, and more team members added close to the magnified players in clear view. For example, we can see that new players such as Bowen, House, and Davis (from Miami Heat) as well as Anderson, Barry, and Pollard (from Sacramento Kings) appear in the zoom-in view. We can also observe that the global context is preserved and words remain legible because several relatively less important players (such as Oakley and Williams around Carter in the bottom left of Figure 5(a)) were removed to make room for the more important ones.

Figure 5.

Word clouds of NBA players in the 2000–2001 season. (a) An initial word cloud of 29 NBA teams represented by top players, where the players from Miami Heat and Sacramento Kings are highlighted by ovals. (b) The focus + context display semantically zooms in to Miami Heat (in cyan) and Sacramento Kings (in orange). In addition to the top players shown in (a), more players from the two selected teams are shown close to the magnified top players in (b).

Quantitative study

In the above case studies, we show that our system can preserve a consistent look before and after switching the focus and context, while keeping all words within the display area and free of overlaps. Now we present a quantitative evaluation to study how our overlap removal method performs compared with a competing method in terms of generating consistent layouts. Among several existing overlap removal algorithms, the closest to our work is the force-directed model proposed by Cui et al.² Aiming at maintaining the topology of a Delaunay triangulated graph while removing empty space between the words, the graph-based force-directed model in Cui et al.² (denoted as GFD) consists of three forces: a spring force (for removing empty space between two words), a repulsive force (for removing overlap between two words), and an attractive force (for penalizing triangle flips). We compared the performance and quality of GFD and our constraint-based force-directed model (denoted as CFD)—both were implemented using JavaScript and HTML5. The dataset in use is the same as in the case studies. All the results were generated in Google Chrome on an Intel Core i7-2600 CPU at 3.40 GHz desktop.

Besides measuring the computational performance of the two methods, we employed three metrics adapted from Strobelt et al.²⁹ to measure their quality, namely, Euclidean displacement, orthogonal ordering, and size increase.

Euclidean displacement (ED) is a typical metric to measure the proximity relation between two layouts.^2,29 Given an original layout L, a resulting layout $L'$ , and the display space $Γ$ , the normalized Euclidean displacement can be computed as

ED (L, L') = \sum_{i = 1}^{N} \frac{| | L (i) - L' (i) | |}{N \sqrt{Γ}}

where $L (i)$ and $L' (i)$ are the coordinates of word i in L and $L'$ , respectively, and N is the number of words.

Orthogonal ordering (OO) measures the percentage of pairs of words that have the same directional relation between two layouts L and $L'$ . The percentage of preserved orthogonal ordering between L and $L'$ is defined as

\begin{matrix} OO (L, L') = \frac{2}{N (N - 1)} \sum_{i < j}^{N} {dir}_{x} (i, j) {dir}_{y} (i, j) \\ {dir}_{x} (i, j) = {\begin{matrix} 0, if (x_{i} - x_{j}) (x'_{i} - x'_{j}) < 0 \\ 1, otherwise \end{matrix} \end{matrix}

where i and j represent two different words, $x_{i}$ is the x coordinate of word i, and N is the number of words. $di r_{y} (i, j)$ is defined similarly to $di r_{x} (i, j)$ .

Size increase (SI) measures the size increment in the bounding area A of a word cloud from an original layout L to a resulting layout $L'$

SI (L, L') = \frac{A (L')}{A (L)}

This allows us to determine the relative change in the size of a word cloud and measure how much area is needed to display the representation.

Starting from a compact word cloud containing 442 NBA players (the one we have generated in section “Case study”), we first uniformly scaled the words by the SOS algorithm to obtain a legible word cloud with various degrees of word overlaps. We generated such word clouds with N legible words (N is chosen roughly as 50, 100, 150, …, 400) by adjusting the value of f_legible (in the SOS algorithm) correspondingly. Then, the two methods, CFD and GFD, were tested for overlap removal. GFD stops when there is no overlap between any pair of words. Table 1 summarizes the average values of various measurements for the two methods. While the two methods are equally good for maintaining the orthogonal ordering, CFD yields smaller Euclidean displacement than GFD. One possible reason is that the scaled word clouds are too dense for GFD to work appropriately, without stretching for more space to remove overlaps. In contrast, CFD better handles this problem when trying to preserve the spatial proximity and thus produces a more compact word cloud. While the dependency force in CFD can maintain most directional relations among the words, words close to the boundary may have to be pushed further horizontally or vertically, as a result of the boundary force. The compromise between these two forces explains why CFD preserves a similar (rather than larger) amount of orthogonal ordering in comparison with GFD. In terms of size increases, GFD results in around 54% increment in the size of the word cloud, while CFD roughly keeps the original size. This is consistent with the argument in Cui et al.² that GFD may lead to irregular shapes and thus cannot utilize the available display area very well, due to the increase in the bounding area of the word clouds. Figure 6 shows a visual comparison of the word clouds after removing overlaps with GFD and CFD. We can observe in Figure 6(b) that many words fall either on or outside the boundary of the display space after applying GFD. In contrast, we can see in Figure 6(c) that CFD works better than GFD in preserving the size of the word cloud. While Euclidean displacement and size increases of GFD can be improved by scaling down the layout, doing so would shrink the sizes of words by over 30%, which is clearly unacceptable. The computational performance of the two methods is illustrated in Figure 7. From Figure 7(a), we can see that the CFD usually takes more iterations because the converging condition is stricter than GFD. However, from Figure 7(b), we can observe that in each iteration step, CFD is much more efficient than GFD. This is because GFD needs to update the positions of words under the spring force between any two connected words (in the triangulated graph) with empty space. Therefore, the total computation time of GFD grows more sharply than CFD as the number of words increases (shown in Figure 7(c)). In this sense, CFD is more scalable than GFD for overlap removal within a constrained display space. For instance, it takes roughly 11 s for GFD to remove overlaps of around 400 words, while CFD only takes about 1 s. In summary, while preserving similar directional relation in comparison with GFD, CFD is more effective in preserving the spatial proximity and the size of the word clouds. CFD is also more efficient for removing overlaps while maintaining the positional dependencies and constraints.

Table 1.

Average values of the quantitative measurement for the force-directed model in Cui et al.² (GFD) and our force-directed model (CFD).

Method	GFD	CFD
Euclidean displacement	0.1955	0.0916
Orthogonal ordering	0.9137	0.9132
Size increase	1.5393	0.9832

GFD: graph-based force-directed model; CFD: constraint-based force-directed model.

Compared with GFD, CFD yields smaller Euclidean displacement and size increase and performs similarly in preserving orthogonal ordering.

Figure 6.

Comparison of two force-directed algorithms: (a) a word cloud after space-optimized scaling, (b) a word cloud created from (a) using a previous force-directed model in Cui et al.² (GFD), and (c) a word cloud created from (a) using our constrained force-directed model (CFD).

Figure 7.

Comparisons of algorithm speed between the force-directed model in Cui et al.² (GFD) and our force-directed model (CFD) with varying numbers of words: (a) the number of total iterations, (b) the averaged time spent in each iteration, and (c) the total CPU time.

Conclusion and future work

In this article, we introduce a focus + context display technique to support multifaceted viewing of word clouds. Our design provides a balance between displaying the local detail at the focus of the user’s interest and the global context, by taking into account the multifaceted importance of the words. In our algorithm, the sizes of words in a word cloud are first changed to reflect the current importance metric selected by the user and then scaled to balance space utilization and word readability. To remove word overlaps caused by changes of sizes while maintaining the positional dependency modeled by a DAG, we propose a force-directed model that also maximizes the utilization of display space. We show the usefulness of our techniques through case studies on NBA player data and quantitatively study how the force-directed model performs in constraint-based overlap removal. One lesson we have learned is that focus + context methods inevitably need to make a trade-off between details and context. When too many foci are selected simultaneously, the context may have to be sacrificed. Besides, since words of varying sizes are not perfectly aligned, local adjustment based on forces may not produce an optimal packing, compared with space-filling layouts such as Wordle⁷ or ManiWordle.⁸ The proposed SOS algorithm, which utilizes the display space well with decent word readability, could be particularly useful in small displays of mobile phones and pads, where the display space is obviously more precious compared with large displays. In the future, we plan to perform a formal user study to further evaluate the quality of focus + context display techniques for word clouds. We would also like to extend this work to handle more complex word cloud applications, such as dynamic word cloud navigation and hierarchical word cloud exploration.

Footnotes

Acknowledgements

The authors wish to thank the anonymous reviewers for their comments. The NBA dataset used in this article is courtesy of HCIL (Treemap 4.1).

Funding

This work was supported in part by NSF grant IIS-1017635 and IIS-1065025, US Department of Energy grant DOESC0005036, Battelle Contract No. 137365, and Department of Energy SciDAC grant DE-FC02-06ER25779; program manager Lucy Nowell.

References

Collins

Viegas

Wattenberg

. Parallel tag clouds to explore and analyze faceted text corpora. In: IEEE symposium on visual analytics science and technology, 2009, VAST ‘09, Atlantic City, NJ, 12–13 October 2009, pp. 91–98. New York: IEEE.

Cui

Liu

. Context-preserving dynamic word cloud visualization. IEEE Comput Graph 2010; 30: 42–53.

Lee

Riche

Karlson

. SparkClouds: visualizing trends in tag clouds. IEEE T Vis Comput Gr 2010; 16: 1182–1189.

Paulovich

Toledo

FMB

Telles

. Semantic wordification of document collections. Comput Graph Forum 2012; 31: 1145–1153.

Kang

Stasko

. Toward a deeper understanding of the role of interaction in information visualization. IEEE T Vis Comput Gr 2007; 13: 1224–1231.

Thomas

Cook

. Illuminating the path: the research and development agenda for visual analytics. Richland, WA: National Visualization and Analytics Center, 2005.

Viegas

Wattenberg

Feinberg

. Participatory visualization with Wordle. IEEE T Vis Comput Gr 2009; 15: 1137–1144.

Koh

Lee

Kim

. ManiWordle: providing flexible control over Wordle. IEEE T Vis Comput Gr 2010; 16: 1190–1197.

Furnas

. Generalized fisheye views. In: Proceedings of the SIGCHI conference on human factors in computing systems, 1986, CHI ‘86, Boston, MA, 13–17 April 1986.

10.

Bederson

Hollan

. Pad++: a zooming graphical interface for exploring alternate interface physics. In: Proceedings of the 7th annual ACM symposium on user interface software and technology, 1994, UIST ‘94, Los Angeles, CA, 2–4 November 1994, pp. 17–26. New York: ACM.

11.

Viegas

Wattenberg

van Ham

. Many Eyes: a site for visualization at internet scale. IEEE T Vis Comput Gr 2007; 13: 1121–1128.

12.

Lohmann

Ziegler

Tetzlaff

. Comparison of tag cloud layouts: task-related performance and visual exploration. In: Proceedings of the 12th IFIP TC13 international conference on human-computer interaction: part I, 2009, INTERACT ‘09, Uppsala, 24–28 August 2009, pp. 392–404. New York: ACM.

13.

Jaffe

Naaman

Tassa

. Generating summaries and visualization for large collections of geo-referenced photographs. In: Proceedings of the 8th ACM international workshop on multimedia information retrieval, 2006, MIR ‘06, Santa Barbara, CA, 26–27 October 2006, pp. 853–854. New York: ACM.

14.

Kaser

Lemire

. Tag-cloud drawing: algorithms for cloud visualization. In: Proceedings of the 16th international on World Wide Web, 2007, WWW ‘07, Banff, AB, Canada, 8–12 May 2007.

15.

Seifert

Kump

Kienreich

. On the beauty and usability of tag clouds. In: Proceedings of the 12th international conference information visualisation, 2008, IV ‘08, London, 9–11 July 2008, pp. 17–25. New York: IEEE.

16.

Provan

Wei

. Semantic-preserving word clouds by seam carving. Comput Graph Forum 2011; 31: 741–750.

17.

Rivadeneira

Gruen

Muller

. Getting our head in the clouds: toward evaluation studies of tagclouds. In: Proceedings of the SIGCHI conference on human factors in computing systems, 2007, CHI ‘07, San Jose, CA, 28 April–3 May 2007, pp. 995–998. New York: ACM.

18.

Halvey

Keane

. An assessment of tag presentation techniques. In: Proceedings of the 16th international conference on World Wide Web, 2007, WWW ‘07, Banff, AB, Canada, 8–12 May 2007, pp. 1313–1314. New York: ACM.

19.

Spenke

Beilken

Berlage

. Focus: the interactive table for product comparison and selection. In: Proceedings of the 9th annual ACM symposium on user interface software and technology, 1996, UIST ‘96, Seattle, WA, 6–8 November 1996, pp. 41–50. New York: ACM.

20.

Lamping

Rao

Pirolli

. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In: Proceedings of the SIGCHI conference on human factors in computing systems, 1995, CHI ‘95, Denver, CO, 7–11 May 1995, pp. 401–408. New York: ACM.

21.

Munzner

Guimbretière

Tasiran

. Treejuxtaposer: scalable tree comparison using focus+context with guaranteed visibility. In: Proceedings of the 30th international conference on computer graphics and interactive techniques, 2003, SIGGRAPH ‘03, 27–31 July, San Diego, CA, pp. 453–462. New York: ACM.

22.

Kincaid

Lam

. Line graph explorer: scalable display of line graphs using focus+context. In: Proceedings of the working conference on advanced visual interfaces, 2006, AVI ‘06, Venice, 23–26 May 2006, pp. 404–411. New York: ACM.

23.

Carpendale

MST

Sheelagh

Carpendale

. Multi-scale viewing. In: Proceedings of the 23rd annual conference on computer graphics, 1996, SIGGRAPH ’96, New Orleans, LA, 4–9 August 1996.

24.

Shen

H-W

. Balloon focus: a seamless multi-focus+context method for treemaps. IEEE T Vis Comput Gr 2008; 14: 1157–1164.

25.

Wang

Y-S

Chi

M-T

. Focus+context metro maps. IEEE T Vis Comput Gr 2011; 17: 2528–2535.

26.

Preim

Raab

Strothotte

. Coherent zooming of illustrations with 3d-graphics and text. In: Proceedings of the conference on graphics interface, 1997, Kelowna, BC, Canada, 21–23 May 1997, pp. 105–113. New York: ACM.

27.

Stoffel

Strobelt

Deussen

. Document thumbnails with variable text scaling. Comput Graph Forum 2012; 31: 1165–1173.

28.

Liu

. ViSizer: a visualization resizing framework. IEEE T Vis Comput Gr 2013; 19: 278–290.

29.

Strobelt

Spicker

Stoffel

. Rolled-out Wordles: a heuristic method for overlap removal of 2D data representatives. Comput Graph Forum 2012; 31: 1135–1144.

30.

Eppstein

van Kreveld

Speckmann

. Improved grid map layout by point set matching. In: 2013 IEEE Pacific visualization symposium (PacificVis), Sydney, NSW, Australia, 27 February–1 March 2013, pp. 25–32. New York: IEEE.

31.

Dwyer

. Scalable, versatile and simple constrained graph layout. Comput Graph Forum 2009; 28: 991–1006.

32.

Dwyer

Koren

Marriott

. Constrained graph layout by stress majorization and gradient projection. Discrete Math 2009; 309: 1895–1908.

33.

Dwyer

Marriott

Stuckey

. Fast node overlap removal. Lect Notes Comput Sc 2006; 3843: 153–164.

34.

HCIL, University of Maryland. Treemap 4.1, http://www.cs.umd.edu/hcil/treemap/doc4.1/toc.html

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB