Unpackable Treemaps as Web History Graphs

Jennifer Tillett
Department of Computer Science
University of British Columbia
2366 Main Mall
Vancouver, BC, V6T 1Z4, Canada

Domain, Task and Dataset
Personal Expertise
Proposed Infovis Solution
Scenario of Use
Proposed Implementation Approach


Domain, Task and Dataset

Web browsing is a well-established domain in which millions of users are active every day. For most casual users and browsing tasks, the history devices provided with a browser, such as bookmarks, "Back" and "Next buttons and a list of sites visited divided by day or week, are sufficient. However, when the browsing task becomes large or complex, traditional history presentation techniques fail. Users become disoriented among large sets of web pages, forgetting which pages were visited for what search and in what order as well as the content of pages. A map of the visited pages will help the user keep track of her web-browsing, and hopefully find desired content more quickly.

Many techniques have been advanced for graphing the history of a user's browsing, including a zooming web browser in Pad++ with edge-node tree structure by Bederson et. al. [1], an interactive "navigation map" using an node-link graph by Zeiliger [2], WebMap by Doemel [3], WebOFDAV, which creates a node-link graph of actual browsing and inferred connections to the rest of the World Wide Web [4], as well as multiple three dimensional visualizations.


Personal Expertise

I have been browsing the web for about 10 years. I had never studied information visualization until I took CPSC 533. I have experience in computer graphics and object-oriented programming.


Proposed Infovis Solution

The task of visualizing a web browser's history can be tackled using treemaps. A description and history of treemaps is maintained by Ben Schneiderman [5]. Squarified treemaps [6] maintain node shapes and sizes that are appropriate for displaying information. Nested treemaps show the underlying tree structure of a treemap by nesting child nodes inside parent nodes, leaving a small border to reveal the context. I propose a new kind of treemap, which can be "unpacked" on request to reveal the underlying tree structure, thus improving the context problems inherent in treemaps [Figure 1]. This feature is also important for my task, as parent nodes are not simply containers for data, they are web pages themselves, and displaying them as an entire node, rather than just borders, will allow their information to be displayed. Implementing this feature will also require distortion techniques, for preserving the treemap structure while increasing the number of nodes displayed [Figure 2], and possibly zooming. Nodes of the treemap will display identifying bits of the web pages they represent -- deciding which bits will convey the most information is part of the infovis challenge. Cycles in the graph will be handled by maintaining only one node for each page that is allowed to have children (which is designated as the instance of the page that was visited first), with other instances of the page becoming leaf nodes and being highlighted to indicate that they are multiples [Figure 3].

Figure 1: (a) Treemap before unpacking. Nodes D1, D5 and D are beneath the D leaf nodes. (b) Treemap after "unpacking" parents of the D leaf nodes.

Figure 2: (a) Treemap before B3 is unpacked. (b) When the white arrow is clicked, B3 is unpacked, revealing its parents, and the rest of the treemap is distorted to accommodate the expansion.

Figure 3: (a) User is about to click a hyperlink to cycle back to 'A'. (b) 'A' becomes a leaf node, but any further navigation is done from the first instance of 'A', which gets the focus.

Scenario of Use

Suzie is browsing the web. She would like to record an interactive history of her browsing, but finds the "Back" and "Forward" lists to be too narrow in their scope, because they only record linear progress. Her "History" tree simply groups pages by their domains, which doesn't preserve either linearity or any other progression. She decides to try an interactive history graphing application, namely Unpackable Treemaps. To use it, she starts the Unpackable Treemap applet and a browser window.

When she begins browsing, the first page she loads is displayed as the first node in the treemap. Because there are no other nodes, this page can take up the whole of the applet's visual space. As she follows hyperlinks, more nodes will be added to the right side of the treemap while older nodes move to the left and are possibly reduced in size. If Suzie visits more pages than can be legibly displayed, older nodes will be "packed" away, sliding under newer nodes to the right [Figure 4]. The nodes remaining which are contained in hidden nodes will feature an arrow on the left side of the node, indicating that Suzie can click to restore the hidden nodes to the visual space.

If Suzie ever backtracks to a page she has visited before, and then follows a different hyperlink to the next page she'll browse, the treemap will be updated with another series of nodes coming from the revisited page [Figure 5]. Pages which have siblings will feature arrows at the top or bottom (or both) of the page, which the user can click for a list of the siblings -- this list is also clickable, for navigation to siblings. Cycles in Suzie's browsing will be handled as explained in the previous section [Figure 3].

When Suzie wants to explore her treemap, she can click the "expand" or "unpack" tool button. At this point, her cursor becomes an unpacking lens, and moving over edges of nodes with parents or siblings will unpack any underlying nodes in the fashion described in the previous section [Figures 1 & 2]. Suzie should also be allowed to zoom in or out for more detail.

To allow Suzie the same navigation benefits as a standard web history widget, several features are included. When Suzie wishes to view a page in her web browser, she can double-click on a node. Hovering over a node pops up a box with more information about the web page. Suzie can indicate "Favorites" or "Bookmarks" which are sites she thinks she would like to return to later -- these can be displayed upon request by highlighting the bookmarked nodes, or the box containing the same leaf nodes that the bookmarked node contains. Figure 6 illustrates a potential screen layout for the application.

Figure 4: Using the example from Figure 3, when hyperlink 'A' is selected and leaf node 'A' is added while original node 'A' gets the focus, older nodes 'Z' and 'Y' are shifted behind 'A'. An arrow on the left side of 'A' indicates that it has parent nodes which can be displayed.

Figure 5: (a) The user has navigated back to a previously visited node, 'A', and follows a different hyperlink out of the page, 'H'. (b) The treemap is updated with a new child node for 'A'.

Figure 6: Mock screenshot, featuring unpacking lens tool-button and examples of displaying web page content in nodes.


Proposed Implementation Approach

The treemap will be drawn in Windows with Java by extending the InfoVis Toolkit [7]. The InfoVis Toolkit is an interactive graphics toolkit which supports treemaps. I may also use the Piccolo toolkit [8] for zooming. Piccolo is a successor to Pad++ which offers tools for zoomable interfaces in Java. I have never used either toolkit before.




Establish familiarity with the Infovis Toolkit.


Implement a treemap web history graph.


(a) Experiment with legibility of web page information in nodes.

(b) Add unpacking capability.

(c) Add cycle visualization.

(d) Add zooming.



Benjamin B. Bederson, James D. Hollan, Jason Stewart, David Rogers, David Vick A Zooming Web Browser


Romain Zeiliger, Claire Belisle, Teresa Cerratto Implementing a Constructivist Approach to Web Navigation support.




Mao Lin Huang, Peter Eades and Robert F. Cohen WebOFDAV navigating and visualizing the Web on-line with animated context swapping.


Ben Shneiderman Treemaps for space-constrained visualization of hierarchies.


Mark Bruls, Kees Huizing, and Jarke J. vanWijk. Squarified Treemaps.


Jean-Daniel Fekete. The InfoVis Toolkit. Version 0.7alpha1, 2004. http://ivtk.sourceforge.net//


Piccolo Toolkit