© Copyright ACM 1997
However, today's design of history mechanisms tend toward ad-hoc approaches that do not appear to take advantage of previous research into history support within user interfaces [e.g., 5,6]. In particular, their designs are not based upon actual studies of how people revisit web pages, and their actual use has been examined only superficially.
Our goal is to place the design of history mechanisms within browsers on an empirical foundation. We had two sub-goals.
This paper summarizes our findings. A thesis  and journal paper  provides further detail, a review of history mechanisms, and guidelines for browser redesign.
XMosaic 2.6 was modified to record a user's browsing activity. Each activity record included time, URL visited, page title, final action, method of invoking the action, user id, and several other items. Volunteer participants then used the browser for approximately six weeks; all were practiced web users with at least one year of experience (see  for details of subject selection). At the end of the study, we analyzed logs from 23 participants. This was followed by hour-long individual interviews, done to gather qualitative data about personal browsing methods and to help use understand why the patterns seen in the analysis arose.
Six analyses pertaining to web page reuse are presented here. We begin by reporting the rate that web pages are revisited. The remaining analyses concern five different patterns that may suggest effective approaches to presenting revisited pages for future access. First, we examine how users visit both old and new web pages over time. Second, we look at the distance (in terms of URLs) between repeated visits to the same URL. Third, we assess the frequency of URL visits. Fourth, we determine the extent to which users repeatedly browse within locality sets (page clusters). Last, we identify repeated sequences of URLs as an estimate of path-following behaviour.
History mechanisms within web browsers are only useful if users actually repeat their activities. Yet we do not know how often people revisit their pages. This is important, as it gives us a bound for how useful a history mechanism can be. In other domains, research has quantified this repetition of user actions  e.g., telephone numbers dialed (57%), how information is retrieved in a technical manual (50%), and how Unix command lines are entered (75%. We analyzed our own data and the Catledge and Pitkow  data to derive the recurrence rate R: the probability that any URL visited is a repeat of a previous visit. Each user's data was analyzed independently, and the statistics below represent either averages across all users, or representative individuals.
We found an overall recurrence rate of R=58% (standard deviation = 9%) for our 23 subjects, and 61% (standard deviation = 9%) for 55 subjects from the Catledge and Pitkow study. These numbers clearly show that users revisit web pages heavily, although it also means that ~40% of all page navigations are to new pages. These recurrence rates qualify web browsing activity as a recurrent system. Greenberg  coined this term to characterize systems where users predominately repeat activities they had invoked before, while still selecting new actions from the many that are possible.
In post-study interviews, people gave us their major reasons for visiting new pages and revisiting old ones. They revisit pages because: the information contained by them changes; they wish to explore the page further; the page has a special purpose (e.g. search engine, home page); they are authoring a page; or the page is on a path to another revisited page. People visit new pages because: their information needs change; they wish to explore a particular site; a page is recommended by a colleague; or they notice an interesting page while browsing for another item.
Since web browsing is a recurrent system, we believe that browser interfaces should support page revisits by minimizing a user's effort to return to a page when compared to the effort of navigating there from scratch. The key is to give preferential treatment to the large number of repeated actions. This involves identifying patterns in history use, as discussed in subsequent sections.
The first pattern considered shows the distribution of old and new page visits over time. We generated vocabulary graphs for each subject, where the URL vocabulary-the number of unique URLs seen so far-is plotted over the total number of URLs visited. These plots illustrate how users extend their vocabularies, and how recurrences are distributed over time.
For example, Figure 1 shows the plot for participant 15. The curve All represents the overall URL vocabulary size at any moment in time. Major navigation actions are also plotted as separate curves shifted above the vocabulary line by a constant amount (for ease of illustration): Open URL, Back, Reload, Forms, and Helper Applications. The Other category includes all remaining navigation actions. These curves show when the most common navigation actions were invoked and, taken together, comprise the All curve.
Figure 1. URL Vocabulary for participant 15
URL vocabulary growth graphs for all subjects exhibit a linear slope, typified by the line in Figure 1. Both data and interviews indicate that users incorporate new URLs into their repertoire at a regular rate, and that revisits are fairly evenly distributed.
These plots are only roughly linear, and many local variations to the slope are also evident. We noticed that the nature and extent of these vary amongst individuals. We analyzed these variations and their corresponding navigation actions, and asked participants questions about them during interviews. Consequently, we identified seven browsing patterns, four of which are illustrated in Figure 1.
Three other browsing patterns were seen in other subjects.
Browsers and history mechanisms should support the many browsing patterns users exhibit. For example, stack-based history mechanisms and the Back button found in most browsers supports both hub-and-spoke and depth-first search patterns. The Reload button is very convenient for authoring. Guided tours contain hyperlinks that encourage a linear pattern of navigation. Yet improvements in history designs are possible. Perhaps the excessive backtracking that results from depth-first navigation styles and the hub-and-spoke could be reduced by a graphical overview map, or by retaining the index page within the browser window, as often done with Netscape Navigator 2.0's frames feature.
In this section, we saw that both old and new web pages are visited regularly over time. The huge number of pages in the vocabulary implies that we cannot simply offer all previously visited pages within a visual history mechanism, as this would be unmanageable. Instead, we must offer the user only a handful of candidate pages that have a high probability of being revisited. Researchers in other domains have noticed that recently used actions are the ones most likely to be repeated [5,6]. This warrants an investigation into recency effects by considering URL visits as a function of distance.
For any URL visited, the probability that it has already been seen by the user is quite high (R=58%). But how do particular URLs contribute to this probability? Do all URLs visited have a uniform probability of recurring, or do the most recently visited URLs skew the distribution? If a graphical history mechanism displayed the previous p page titles or URLs as a list, what is the probability that this includes the next page to be visited ?
The recurrence distribution as a measure of distance was calculated for each subject. Distance is determined by counting the number of items between the current URL being visited from its first match on the history list. For example, a distance of 1 occurs when the user reloads the current page, or successfully interrupts the transmission of a page. A distance of two occurs when the current page is a revisit to the one seen two pages ago. Figure 2 plots this data up to a distance of 50, averaged across all subjects. The horizontal axis shows the distance of the repeated URL on the history list relative to the one being entered. The vertical axis represents the rate of URL recurrence at a particular distance, denoted as Rd. According to Figure 2, there is a Rd1 = 10% probability that the current URL is a repeat of the previous URL (distance = 1), Rd2 = 19% for a distance of 2, Rd3 = 2%, Rd4 = 5%, and so on. The spikes at distances of 2, 4, 6 and 8 arise from users' navigating back to previous pages by the 'Back' navigation action.
Figure 2a. URL recurrence rate as a function of distance (all participants)
Figure 2b. As above, but plots recurrence rate as a running sum
The most striking feature of this data is the extreme recency of the distribution. The 6 or so URLs just visited contain the majority of pages visited next, although the probability values of Rd rapidly decrease after the second item. Beyond a distance of 8, the low values (< 1% each) and low rate of decrease make items equivalent for practical purposes.
This is illustrated further in the inset of Figure 2, which reports the same data for all subjects as a running sum of the probability, denoted as RD. The horizontal line at the top of the graph is the maximum mean recurrence rate for all subjects of 58%. The most recently visited URLs are responsible for most of the cumulative probabilities. For example, there is an RD6=39% chance that the next URL visited will match a member of a set containing the 6 previous submissions. In comparison, all further contributions are slight (though their sum total is not).
Frequency is a popular method for ranking items of interest. We examined this pattern in two ways. First, we generated a frequency graph for each subject. Second, we developed a taxonomy of conceptual page types for frequently visited pages from our post-study interviews.
All subjects produced a similar frequency distribution, where only a small number of URLs are highly visited, and a very large number of URLs have very low usage frequencies. Over all subjects, 60% of pages were only visited once, 19% were visited twice, 8% were visited 3 times, and 4% were visited 4 times. Relatively few pages were frequently accessed, and these tend to fall into categories that explained their popularity: personal pages, start-up documents, indices, search engines, individual and organization home pages, web applications, navigation pages, and authored pages.
While recency characterizes recurrences in terms of distance, locality considers recurrences in terms of periods of time where repeated references are made solely to a small and related group of items, called a locality set . We applied the locality detection algorithm  to the WWW data to determine whether users generate locality sets, that is, whether they browse within clusters of pages.
While locality sets were found [8,9], they do not appear to offer much value in terms of predicting the user's next activity within web browsing. There are several reasons for this claim. First, most locality sets were very small, consisting of only one or two unique URLs. Second, these sets lasted for only a short time, usually 2.5 to 4.5 URLs. Third, few locality sets were repeated; those that were repeated tended to be of size one or two. Fourth, only 15% of URLs visited were part of a locality set.
The concept of paths, an ordered traversal of hypertext links, has been associated with hypertext ever since Vannevar Bush envisioned hypertext in 1945 . If paths exist, it may be useful to capture and offer them via history, thus simplifying people's efforts to retrace a path. Also, if users follow paths solely as a route to a destination, shortcuts could allow a user to go directly there.
We applied the Pattern Detection Module (PDM) algorithm  to the WWW browsing data in an attempt to identify longest repeated sequences (LRSs) of page visitations. As with locality, we discovered that LRSs are not particularly useful for predicting web browsing for a variety of reasons. We found that though LRSs do exist, they tend to be short [8,9]. The few longer LRSs usually reference only one or two pages as sequence elements. In terms of repetition, the average frequency for LRSs of all lengths hovered around two which is the minimum requirement to be considered a LRS. Also, there is a strong recency effect: repeats of LRSs occur within a short distance of each other.
The recurrence distributions used above were derived by creating a trace of all page visits for a user with no barriers placed between browsing sessions. We have seen that although a small set of recently visited URLs accounts for a high proportion of revisits, others lie outside. Consider a set of the 10 previous URLs on the history list. From the inset in Figure 2, there is a 42% chance that the next URL the user would like to visit has not appeared before, an RD10=43% chance that it has occurred within the last 10 visits, and a 15% chance that it appeared at distances greater than 10. This section explores the possibility that the distribution can be conditioned, first to increase the recurrence probabilities over a set of a given size, and second to evaluate methods that are currently in use. Eight conditioning methods are presented within four major categories: recency, frequency, stack, and hierarchically structured. A later results section will consider how effective each method is.
We will illustrate these methods by using the small sample trace in Table 1, which shows the last 16 pages visited by a user. Pages are numbered by order of visit, with #16 being the most recently visited page. The user's action to navigate to those pages are shown on the right. Italicized pages are revisits. Each conditioning method is then applied to this trace, and the ordering of items that will be shown to the user in the conditioned history list is given in Table 2.
|Visit # URL||Action|
|16 acsl.cs.uicu.edu/kaplan/applets||Open URL|
|15 acsl.cs.uicu.edu/kaplan/worlds-environ||Open URL|
|14 acsl.cs.uicu.edu/kaplan/worlds||Open Hotlist|
|13 www.acm.org/sigchi/chi96/forms/Proc||Open URL|
|12 www.acm.org/sigchi/chi96/call/index||Open URL|
|11 www.acm.org/sigchi/chi96/||Open URL|
|10 www.acm.org/sigchi/homepage||StartUp Doc.|
|7 www.acm.org/sigchi/cscw96/dates||Open URL|
|6 www.acm.org/sigchi/cscw96/||Open URL|
|3 www.acm.org/sigchi/chi96/Deadlines||Open URL|
|2 www.acm.org/sigchi/chi96/||Open URL|
|1 www.acm.org/sigchi/homepage||StartUp Doc.|
|a) Sequential ordering by recency|
|16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1|
|b) Recency, duplicates in latest position|
|16, 15, 14, 13, 12, 11, 10, 8, 7, 3|
|c) Recency, duplicates in original position|
|16, 15, 14, 13, 12, 7, 6, 3, 2, 1|
|d) Frequency, second key recency 10, 11, 8, 16, 15, 14, 13, 12, 7, 3|
|e) Stack, non-persistent 16, 15, 14, 13, 12, 11, 10||f) Stack, persistent 16, 15, 14, 13, 12, 11, 10, 1|
|g) Context-sensitive Web subspace||h) Hyperlink sublist
(session 1 only)
|14 (16, 15)||16||12 (13)||7|
|10 (13, 12, 11, 8, 7, 3)||15 (16)||11 (12, 3)||3|
|14 (15)||10 (11, 6)|
Three types of recency ordered history lists were evaluated. The first is sequential ordering, the time-ordered list of all URLs visited by the user, including revisits to the same URL. Thus the history list as shown in Table 2a is a literal trace, and is an exact match to the trace in Table 1.
The problem is that repeated items have multiple entries, which occupy valuable space on a history list of a limited length. Hence, two strategies for pruning redundant URLs were applied: saving the URL only in its original position on the history list, and saving the URL only in its latest position. Tables 2b and 2c provide an example of both approaches to pruning duplicates. Note that there are fewer URLs on these lists as compared to the strict sequential version that retains all URLs. Also, note that the user's StartUp document (a heavily accessed page) occupies the bottom position on the list (#1) when URLs are saved in their original position, while it is propagated up the list when they are saved in the latest position (#10). Thus we expect the 'latest position' approach to perform better, because just revisited URLs will stay at the top of the list (whereas they migrate to the bottom on 'original position'), and because local context is maintained .
Greenberg  claims two benefits of recency-based history. First, the URLs presented are the ones the user has just visited. Thus, the user will remember and can effectively predict which URLs will appear on the list. Second, recency does not suffer from the initial startup instability that other methods do when there are only a few URLs available to present to the user.
Frequency ordering, where the most revisited page appears at the top of list and the least visited page appears at the bottom, is an obvious way of ranking URLs. Frequency ordering could be problematic. While user's needs and interests change quickly, the newer URLs need to be revisited frequently before they can migrate to the top of the list. Similarly, older frequently used items that are no longer of interest remain near the top. Still, there are certain types of pages that users tend to frequent regularly, and perhaps we can expect useful offerings of frequency ordering after periods of extended browsing (which stabilizes the frequency distribution).
An issue associated with frequency ordering is how to break ties with URLs that have the same frequency. Greenberg  evaluated two schemes for secondary sorting within frequency ordered lists: recency and reverse-recency. Recency was found to perform better so that is the method of secondary sorting that we have applied. Table 2d shows the effect of frequency ordering with secondary sorting by recency upon the navigation session in Table 1.
Current web browsers maintain a history list that operates as a stack; the most recently visited page is usually pushed onto the top of the stack, so older pages appear underneath. Unlike recency, pages can be popped off the stack and lost. The way browsers push and pop pages from the stack depends upon three techniques the user employs for displaying the page: loading, recalling, and revisiting . In this terminology, loading a page causes it to be added to the top of the stack, possibly resulting in all pages above the current position to be lost. Recalling a page changes the pointer to the currently displayed page in the stack. Revisiting a page occurs when the user reloads the page, and has no effect upon the stack.
We expect that the stack method will perform reasonably well for very short recurrence distances, as it will appear similar to recency. It will lag at modest distances because some recent URLs are popped off the stack when the user loads a page while at some point other than the stack's top. It will do poorly for long distances because current browsers clear the stack between sessions. Table 2e shows the history list based on this sessional stack at the end of the example navigation session. Note that the trace in Table 1 shows that a new session started on page #10 (indicated by the startup document action), so earlier pages are lost.
Because we may want to revisit pages from previous sessions, we constructed a persistent stack that retains the stack from the prior session. While the persistent stack will perform similar to the sessional stack for short distances, it should do better for long distances because some URLs are retained between sessions. Still we do not expect this method to perform better than recency ordering with no duplicates due to the absence of some URLs. Also, the persistent stack will be longer than necessary due to the presence of duplicates. Table 2f shows this persistent stack; it now includes a pointer to a page from the first session.
Two methods that employ hierarchical structuring were examined: recency ordered hyperlink sublists, and context-sensitive web subspace history lists.
Recency ordered hyperlink sublists is similar to the recency ordered history list with duplicates saved only in their latest accessed position. The difference is that for each URL on the normal list, a secondary recency-based history list can be raised containing only those pages that the user had visited by selecting a hyperlink from the current page. The user first scans down i entries in the normal list for an exact match that terminates the search, or for an entry that contains the desired hyperlink. In the latter case, the sublist of hyperlinks is displayed (perhaps as a cascading menu) and the search continues until an exact match is found j entries later. The distance of a matching recurrence is simply i + j. Table 1h shows the hyperlink sublist. The hierarchy in this example is not very full because it is generated from a short trace; we expect that longer traces would fill the slots in the secondary lists.
We expect recency ordered sublists to perform better than recency with duplicates saved in their latest position. First, more URLs are accessible through a hierarchy. Second, if the user needed to visit a page only because it contained a hyperlink to the desired page, that page can now be selected directly from a sublist. Third, because sublists contain only URLs that the user has already accessed from a particular page, the user may find it easier to find a specific URL on the sublist, especially if the jump-off page is long and contains many irrelevant links.
The context-sensitive web subspaceis based upon a graphical history display designed by Cockburn and Jones . The display creates a new web 'subspace' each time the user directly accesses a page. This page is added as an item in a webs menu. Any pages accessed until the next directly-accessed page (the subspace) are added to a secondary menu that cascades from the original webs menu entry. For our analysis, we considered the following actions as a direct access to a URL: typing a URL, selecting a Hotlist item, cloning or opening a new window, and accessing a URL via client-dependent hard-wired buttons or menus. Within the main and secondary menu, we sort the URLs based on recency, and remove duplicates, saving according to the latest position. A URL can thus occur only once in the main menu or a particular secondary menu, but it may be found within several subspaces if the user navigated to it in different ways. This is appropriate since subspaces seem to be a reasonable method for inferring a user's context when browsing. That is, when the user follows a series of hyperlinks, many of the pages visited will tend to be related in some way.
Table 1g shows the history list at the end of the navigation session. There are 2 URLs in the main menu indicating that 2 different URLs were direct accessed (the StartUp Document and the Open Hotlist). The last subspace the user browsed is located at the top of the list. The sublists show the contents of the web subspace sorted in recency order.
We evaluated all methods described above. We took our subjects' traces, and implemented algorithms to process the trace so that it simulated a userís optimal use of a selected method. Our evaluation accounts for the following factors.
A strict sequential list of URLs ordered by recency performs reasonably well when ten URLs are listed e.g. RD10 = 43% vs. the upper bound of 58%. A benefit of this method is that its conceptual model is simple and familiar. That is, a person knows what they have just done and can thus predict if an item will be on the history list. We will use this value as a benchmark to contrast other methods.
Pruning duplicates is a simple way of improving the performance of a recency-ordered list when duplicates are saved only in their latest position (RD10 = 47% vs. 43% for strict recency). While this type of list does not show the exact sequence of URLs visited by the user, it still presents a clear conceptual model, and we expect that the user can easily understand how the lists contents are ordered. Saving duplicates in only their original position is very poor (RD10 = 29%), as frequently used items remain at the bottom. The striking differences between these three recency orders are illustrated by the plots in Figure 3.
Figure 3. Cumulative probabilities of recurrences over distances up to 50
Frequency ordering is the worst predictor of the 8 evaluated for short lists, with RD10 = 27% vs. 43%. While it does improve as distance is increased, it does not catch up to strict recency (Figure 3). Frequency has other problems. Users may find it more difficult to predict which pages would appear on a frequency-ordered list beyond the two or three that they visit the most. As well, frequency ordering suffers instability when few items are on the history list, and excessive inertia when the list is long. Still, frequency could be applied to a few key URLs, possibly used as an auxiliary method in conjunction with another history mechanism that gives better overall performance.
The sessional stack method found in most web browsers is slightly better than strict recency at very short distances (RD5 = 40% vs. 37%) and slightly worse at RD10 (42% vs. 43%). As seen in Figure 3, it is much worse as the list gets long. The persistent stack is an improvement over the stack and strict recency methods in terms of its recurrence probabilities over distance (RD10 = 47% vs. 43%). Both approaches suffer problems as users typically form an incorrect conceptual model with this method-Cockburn and Jones  discovered in their usability study that users were often surprised at the behaviour of their history list, and they could not predict how it worked. Because other methods are equal or better than even the persistent stack in terms of predictiveness (such as recency with duplicates removed), they are better choices.
Recency ordered hyperlink sublists have the highest recurrence probability over all methods for very short distances (2-4), and are second best at modest distances (RD10 = 51% vs. 43%). The catch is that this result is optimistic, since a person requires greater cognitive and physical effort to select items from the hyperlink sublists e.g., to make an accurate selection from a hyperlink sublist, the user must recall which main list item contains the desired URL. Also, note that hyperlink sublists can provide access up to 55 URLs for a RD10 (the main list of 10 items + 9 items on sublist one + 8 items on sublist two + 7 items on sublist three, etc.).
The best method we evaluated-context-sensitive web subspaces-showed that 53% of all URL selections can be successfully predicted with a set of 10 items. Given that R = 58% on average, which is the best a perfect reuse facility could achieve, this method is ~91% effective. The caveat is similar to hyperlink sublists, as users of context-sensitive web subspaces require greater physical effort to select a sublist item, and greater cognitive effort to recall which sublist might contain the URL. In addition, users may have more difficulty understanding how this method works, as they need to know what a 'direct access URL' is to grasp the way the history list is organized .
In conclusion, our analysis of conditioning methods shows that several methods improve upon the effectiveness of current stack-based history mechanisms. As seen in Figure 3, recency is a simple yet reasonable predictor, especially when duplicates are saved only in their latest position. A further appeal of recency is that it is conceptually easy for a user to understand. While the two hierarchical methods are better predictors, we suspect that they may not work as well in practice due to the extra physical and cognitive overheads mentioned earlier. Further research is required to evaluate these methods in actual use.
We collected usage data on three history mechanisms found in Mosaic: backtracking through the Back button, stack-based history lists, and personalized hotlists of URLs.
The success of 'Back' is in line with our observation that extreme recency is a good predictor of what pages will be revisited. The poor use of other history facilities is likely due to interface issues. For example, hotlists require considerable effort to manage: users may not bother to add an URL to the list, may forget that it is there, or only record URLs that are convenient starting points. The 'Window History' in Mosaic 2.6 is not visible and requires several actions to access. Because it is based on the stack model, the desired URL may have been popped off the list even though it was entered a short time ago.
Based on these results we formulate some empirically-based generalizations of how users revisit pages using features found in a typical WWW browser such as Mosaic.
We have developled guidelines for graphical web browser history mechanism design based on the principles above and from general principles on reuse . Our guidelines address: access to pages the user has visited; reducing the cognitive and physical effort of using a history mechanism; providing a reasonable set of candidates for reuse; improving the conditioning method; supporting alternative strategies; and allowing end-user customization of the history data. Full details are provided in .
This paper provided empirical data that justifies the need for suitable history mechanisms in graphical web browsers. Our analysis of different designs proves that the predictiveness of the current stack-based model can be improved upon. Using the methodology and principles herein, designers can refine current history mechanisms and investigate new approaches.
There are still many unanswered questions. We have not evaluated the physical and cognitive effort for reviewing a particular conditioned set of history list predictions. Also, we have not assessed the impact of different browser and HTML artifacts upon reuse such as frames, although we suspect that the numbers reported here would not change dramatically.