Unpackable Treemaps as Web History Graphs
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. , an interactive "navigation map" using an node-link graph by Zeiliger , WebMap by Doemel , WebOFDAV, which creates a node-link graph of actual browsing and inferred connections to the rest of the World Wide Web , as well as multiple three dimensional visualizations.
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.
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 . Squarified treemaps  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].
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.
The treemap will be drawn in Windows with Java by extending the InfoVis Toolkit . The InfoVis Toolkit is an interactive graphics toolkit which supports treemaps. I may also use the Piccolo toolkit  for zooming. Piccolo is a successor to Pad++ which offers tools for zoomable interfaces in Java. I have never used either toolkit before.