ABSTRACT 
   The notion of a surf map, which dynamically graphs pages a user visits while surfing the web, is described and compared to the more common notion of site maps.  It is claimed that the average case growth complexity of links given n pages is O(n).

INTRODUCTION
   Getting lost in a hypertextual medium such as the world wide web is a very common occurance.  To help users navigate and orient themselves, web sites often offer site maps which show the relationships between web pages in a web site.  The most natural approach is to use a graph where nodes and links represent web pages and hyperlinks, respectively.  However, since each page on a site with n pages can potentially link to O(n) pages, the number of links grows as O(n²) for a site map.  The resulting graph is likely to be visually cluttered.
   Nonetheless, because site maps can be invaluable for navigating complicated web sites, various approaches have been taken to provide similar tools without the drawbacks.  Discarding links can result in a visually cleaner, if incomplete, site map [1] while utilizing a folder-tree hierarchy can provide a familiar, if restrictive, interface [2].  More creative
solutions turn to neural networks [3] or the use of pseudo 3D index card layouts [4]. 
   It seems unfortunate, although perhaps an unavoidable consequence, that large web sites - which typically need site maps the most - so easily overwhelm graphs that serve to represent them.  This is unfortunate because graphs are such a natural visual counterpart to the web.  But site maps are not the only tools that require a visualization of the web.  In fact, as useful as they are in providing much needed overviews of web sites, they are limited by the fact that they are fixed to a given collection of web pages.  Following a link to a web page off the web site effectively renders the site map irrelevant.  What is needed is a navigational tool that follows the user anywhere on the world wide web.

SURF MAPS
   Like a site map, a surf map is defined over web pages and the links that relate them.  However, rather than a static map that only reflects a pre-defined portion of the world wide web, a surf map is dynamically created and a new node is added to the graph each time the user visits a new web page.  Surf maps are not limited by virtual boundaries that divide the world wide web into separate web sites; all web pages are treated equally. Functionally, surf maps help users return to previously visited web pages with ease and to see the choices made and branches taken which got them to where they are.  Work done in this area includes MosiacG [5], Pad++ [6], and SurfSerf [7].

AVERAGE CASE COMPLEXITY
  Links are added to a surf map as they are taken to retrieve web pages.  Browsers typically reserve a different color for links that point to pages that have been visited  from links that point to unvisited pages.  Additionally, the URL of  a link’s destination is usually visible in a status area of the browser.  Thus, the user has multiple cues indicating whether
following a link will lead to a new page or return to a visited page.  Except for the webmaster checking the integrity of links, it is safe to assume that a typical user will not want to return to a page over and over again simply because a link to that page exists.  (Indeed, it is unrealistic to even expect a user would even know where all the links to a given page can be found on the web.)  If we designate k as the maximum number of times a user will return to a page before ignoring subsequent links to that same page, then the maximum number of links added for a particular page is k for a given surf session.  The number of links for n pages is thus kn and it follows that the number of links in a surf map defined over n pages is O(n), in the average case.

REMARKS
   The O(n) growth rate of links in surf maps makes them more suitable for display as graphs than site maps.  This is a desirable feature since the web is most naturally visualized as a graph network comprising of links and nodes (thus, a “web”).  It should be noted, however, that the dynamic nature of surf maps may offset the advantages gained from a slower growth rate of links: one must be careful to ensure that the addition of new nodes
to the graph only minimally affects the global layout of the graph.  Collective structures (e.g. subgraphs) in the graph that may become familiar to a user are of immeasurable value for maintaining orientation on the web and, as such, should remain intact as much as possible.

CONCLUSION
This paper examined the notion of surf maps and compared the growth rate of links (with respect to the number of pages) to that of site maps.  It is claimed that, in the average case, surf maps behaved better than site maps.  Coupled with the fact that surf maps are not limited to a pre-defined set of web pages, they can serve as practical tools for helping
users navigating the world wide web.

REFERENCES
[1] http://www.braun.com/map.htm
[2] http://www.kobixx.com
[3] http://lislin.gws.uky.edu/Sitemap/
[4] http://www.dynamicdiagrams.com/siteviews.htm
[5] http://www.w3.org/Conferences/WWW4/Papers2/270/
[6] http://www.cs.umd.edu/hcil/pad++/
[7] http://www.serfsurf.com