Access Patterns for Robots and Humans in Web Archives

Although user access patterns on the live web are well-understood, there has been no corresponding study of how users, both humans and robots, access web archives. Based on samples from the Internet Archive's public Wayback Machine, we propose a set of basic usage patterns: Dip (a single access), Slide (the same page at different archive times), Dive (different pages at approximately the same archive time), and Skim (lists of what pages are archived, i.e., TimeMaps). Robots are limited almost exclusively to Dips and Skims, but human accesses are more varied between all four types. Robots outnumber humans 10:1 in terms of sessions, 5:4 in terms of raw HTTP accesses, and 4:1 in terms of megabytes transferred. Robots almost always access TimeMaps (95% of accesses), but humans predominately access the archived web pages themselves (82% of accesses). In terms of unique archived web pages, there is no overall preference for a particular time, but the recent past (within the last year) shows significant repeat accesses.


INTRODUCTION
The web has become an integral part of our lives, shaping how we get news, shop, and communicate. In turn, web archives have become a significant repository of our recent history and cultural heritage. The Internet Archive [19] is the largest and oldest of the various web archives, holding over 240 billion web pages with archives as far back as 1996 [13]. Access to this vast archive is available through the Wayback Machine [30], which sees about 82 million requests per day, based on our dataset.
Previous work has studied how users access the live web [31] and search engines [12], but few studies have investigated how users access web archives. Understanding the current demand for access to web archives can provide insights into how to make the best use of limited archiving and access resources.
In this paper, we provide an analysis of user accesses to a large web archive. We examine a set of anonymized Wayback Machine server access logs from February 2012. We investigate the differences between human and robot accesses of the Wayback Machine, identify four major web archive access patterns, and uncover the temporal preference for web archive access. In particular, we find that robots (such as crawlers and spiders) account for 91% of all sessions and 93% of all page requests. Yet, robots only outnumber humans 5:4 in terms of raw, unfiltered requests and 4:1 in terms of megabytes transferred. Humans download more information per session, as they typically download embedded resources (e.g., images and stylesheets), which robots ignore.
We introduce four basic user access patterns of web archives: Dip, Slide, Dive, and Skim. Dip is requesting for a single URI. Slide is browsing different archived copies of the same URI. Dive is following the hyperlinks of a page, but staying near the same datetime. Skim is requesting only the TimeMaps (list of all archived copies for a specific original resource). Robots exhibit the Dip and Skim patterns equally, both about 49% of their sessions, and almost exclusively request TimeMaps. Humans exhibit the Dip (39%) and Dive (30%) patterns the most and access archived pages significantly more than TimeMaps. This paper is organized as follows. Definitions of important terms and a review of related work on web usage mining and web archive studies are presented in Section 2. Section 3 contains the patterns for accessing web archives along with an explanation and example for each pattern. A description of the Wayback Machine's web server logs, the dataset we used in the analysis, and the methodology of this study are presented in Section 4. Section 5 contains the results from analyzing the Wayback Machine access logs. Future work and conclusions are presented in Section 6.

RELATED WORK
Despite the significance of web archives in preserving web heritage, the aspect of web archive usage has been overlooked. The only previous related work is a study of the search behavior characterization for web archives [7]. We highlight this work, but first we define the terms for our discussion.

Memento Terminology
Memento [33] is an HTTP protocol extension which enables time travel on the web by interlinking the current resources with their prior state. Memento introduces content negotiation in the datetime dimension using a special HTTP header, Accept-Datetime [32]. Memento defines the following terms: • URI-R denotes the original resource. It is the resource as it used to appear on the live web; it may have 0 or more mementos (URI-Ms).
• URI-M is an archived snapshot for the URI-R at a specific datetime, which is called Memento-Datetime. e.g., URI-Mi= URI-R@ti.
• URI-T denotes a TimeMap, a resource that provides a list of mementos (URI-Ms) for a URI-R with their Memento-Datetimes, e.g.,

Web Usage Mining
The breadth and depth of research in the area of web usage mining is massive and increasing [3,14,23,5]. Web usage mining involves discovering usage patterns from web data using data mining [25]. The results obtained from web usage mining can be used in different applications, such as web traffic analysis, site modification, system improvement, personalization, business intelligence, and usage characterization. Our study provides traffic analysis and usage characterization by providing abstract models for accessing web archives.
Adams et al. explored the usage patterns of scientific and historical data repositories [1]. However, their study focused on a variety of archive types (e.g., public vs. private, digital but non-web resources) and does not directly address the issue of archiving the web. The only web usage mining research that has been conducted on the usage of web archives is the study of search behavior characterization of web archives based on a quantitative analysis of the Portuguese Web Archive (PWA) search logs [7]. The authors introduced a comparison between search patterns of web archives and web search engines. Despite the different information needs for web archives and web search engine users, the search patterns for web archives had shown adoption of web search engine technologies. They found that most web archive users conducted short sessions. In our study, the sessions that are composed of one request contribute the most to the number of sessions. One important finding from analyzing the search interactions of the PWA logs is that the users prefer older documents. This is in contrast to what we found, that web archive users have significant repetitions for requests in 2011 (the year prior to our sample).
The challenge that faces web usage mining is detecting the robots who camouflage their identity and pretend to be humans. The robot detection problem has been examined in several studies [27,9,15,11]. Doran et al. characterized robot detection techniques into four categories: syntactical log analysis, traffic pattern analysis, analytical learning techniques, and Turing test systems [10]. We used syntactical log analysis (simple processing by finding the self-identified robots) and traffic pattern analysis (specifying features for contrasting robots with humans).

ABSTRACT MODELS FOR ACCESSING WEB ARCHIVES
Through our analysis, we discovered four major patterns for web archive access. We present the model for each pattern along with an example from the logs in Figures 1-4. Each example consists of three columns: the client IP, the access time, and the requested URI. The times annotating the transition arrows in Figure 2-4 represent the interrequest time in the given examples. Note that we use TM URI-R to denote a TimeMap in the figures. We use Memento terminology (URI-T, URI-M, and URI-R) in the definitions. We refer to the original resource for URI-T and URI-M with URI-R(URI-T) and URI-R(URI-M), respectively.

Pattern 1: Dip
Dip is the pattern where a user accesses only one URI. The request can be for a URI-T (Figure 1

Pattern 2: Slide
Slide is the pattern in which a user accesses the same URI-R at different Memento-Datetimes. In this pattern, the user requests a URI-R and walks through time browsing its different copies ( Figure 2).
Navigation between different URI-Ms can be done in many ways, e.g., directly from URI-M1 to URI-M2 (URI-R@t1 ⇒ URI-R@t2) or from URI-M1 to URI-M2, but in the middle the user returns to the TM URI-R to choose between the available datetimes (URI-R@t1 ⇒ URI-T ⇒ URI-R@t2).

Pattern 3: Dive
Dive is when a user accesses different URI-Rs at nearly the same datetime. In this pattern, the user accesses one URI-R at a specific time, URI-R1@t0, then navigates to different hyperlink(s) of URI-R1's page (e.g., URI-R2@t0) and so on (

METHODOLOGY
In this study, we introduce an analysis of the user access patterns of web archives. The analysis was conducted on the Internet Archive's Wayback Machine access logs. The first step in preparing the Wayback access logs for usage mining was transforming the raw log file into server sessions through web-log preprocessing, which included data cleaning, user identification, and session identification [6]. Then, we performed feature extraction, robot detection, and user access pattern detection.

Wayback Machine Access Logs
A Web server log file is a plain text file that records the activity information of the submitted requests from the users on the web server. The Wayback Machine access logs contain the following fields: client IP, access time, HTTP request method (GET or HEAD), URI, protocol (HTTP), HTTP status code (200, 404, etc.), bytes sent, referring URI, and User-Agent. For privacy purposes, the Internet Archive anonymized the client IP address. A segment from the Wayback Machine server logs, which we will call Wayback access logs, is shown in Figure 5. The first line shows a request for a URI-T. The second line shows a request for a URI-M.

Dataset
The Wayback Machine allows users to browse archived copies of web pages across time. The Wayback access logs were sampled using two probability techniques [29]: cluster sampling, which is choosing a cluster of data randomly, and random sampling, where each sampling unit has an equal chance of being included. We performed cluster sampling by choosing a week (Feb. [2][3][4][5][6][7][8]2012) and random sampling by taking a random slice from each day of the week. Each sample comprised a slice of 2M requests to the Wayback Machine web server. Table 1 shows the characteristics of each dataset. It contains the following features for each sample: • Duration: the difference between the last request time and the first request time of each sample in HH:MM:SS format.
• GET: the percentage of requests that used the GET method.
• Embedded: the percentage of requests that were for embedded resources of web pages (such as images and CSS files, etc.).
• SI Robots: the percentage of requests by self-identified robots based on the User-Agent field.
• NullRef: the percentage of requests that had an empty referral field.
• Cleaned: the percentage of requests remaining after removing requests for embedded resources, HEAD requests, and requests that resulted in status codes other than 200, 404, or 503.
• Sessions: the number of sessions.
The last three columns of the table show the mean, standard deviation, and corresponding standard error between the samples. We use the Feb. 2, 2012 sample in our analysis because as we see from Table 1, it is a representative sample.
In the Feb. 2 sample, we note that HTTP 3xx accounts for 52% of the total number of requests. This is related to the default Wayback Machine behavior. First, the Wayback Machine rewrites all of the hyperlinks of a memento's embedded resources with the mementos's timestamp. Second, in the resolution of these URIs, the Wayback Machine will redirect the request of the embedded resources and hyperlinks to the nearest (timestamp) available memento. Furthermore, the Wayback Machine responds with a 302 status first when the requested URI-R is not available on the Wayback Machine, and then responds with a 404 status.

Data Cleaning
The first step in preprocessing our dataset was data cleaning, i.e., removing log entries that were not needed for the mining process [17,28]. In similar studies for log analysis, robots that identify themselves in the User-Agent field were removed. Because robots crawl web archives intentionally, we did not exclude their requests in the cleaning step. We eliminated the following items which were irrelevant in terms of user behavior: • Requests that were generated automatically by the web browser for embedded resources of the requested web page (such as graphic files, page style files, etc.). • Entries with an HTTP status code other than HTTP 200, 404, or 503. We kept only these because we considered them to be requests executed by the user. • Requests using the HEAD request method (as suggested by [16]). • Static resources of the Internet Archive web site and the URIs of the liveweb service, which the Internet Archive introduces to redirect the user to the live web when the copy is not found on the Wayback Machine. • Invalid requests from web sites which included a link for malformed URI-Rs (for example, about:blank) among their embedded resources, so that each request on their web sites caused automatic requests to the Wayback Machine server. Similar behavior had been detected by Omodei [21].

User Identification
To identify the users, the log files were first sorted by the IP, then by the request time. At first, we identified users by the 2-tuple (IP, User-Agent), but we found instances of malicious robots who not only did not self-identify, but who also changed their User-Agent with every request. There are some legitimate cases for humans to have different User-Agents and the same IP, for instance, two simultaneous users coming from behind a firewall. So, we needed to determine a reasonable threshold for the number of User-Agents per IP to detect malicious robots. Figure 6 shows the relationship between the number of User-Agents per IP and the number of requests per IP (for those IPs with more than one User-Agent). We excluded self-identified robots from the graph to avoid biasing the results. We found only 24 users who had changed their User-Agent field more than 20 times. The median value for the number of User-Agents per IP for the dataset is 3 (excluding users who had one User-Agent only). We concluded that 20 different User-Agents per IP is a good threshold for this dataset. For IPs with at most 20 different User-Agents, we used the 2-tuple (IP, User-Agent) to identify individual users. The 24 IPs with more than 20 different User-Agents were classified as 24 separate robots.

Session Identification
A session is the set of web pages that are requested by particular user [17]. Session identification is performed by dividing a web server log file into web server sessions. First, we group all the requests based on the IP and User-Agent (as described in Section 4.4). Second, we apply a threshold timeout, so that if the time elapsed between two consecutive requests is longer than this threshold, the second request is considered to be the first request of the new session. There have been several suggested timeout thresholds including 25.5 minutes [5], 30 minutes [27,14], and 60 minutes [2]. Others proposed 10 minutes as a conservative threshold to capture the time for staying on one page [16,24]. In our study, we divided the requests of each user into individual sessions based on a 10 minute timeout threshold. Future research is required to verify that searching and browsing models for the current web are valid for browsing the past web (i.e., web archives).
After identifying the sessions, we extracted features for each session to be used further in the analysis. A session, S, is 7-tuple.

Robot Detection
Because of the increasing numbers of web crawlers that are engaged in web harvesting, many studies have been conducted for investigating the robot detection problem [   15]. In this study, we used different types of robot detection techniques [10]. First, we applied syntactical log analysis by checking the User-Agent field to identify the self-identified robots. Second, we applied traffic pattern analysis techniques to distinguish humans from robots based on their navigational behavior. In this section, we describe heuristics we used for distinguishing robots from humans.

User-Agent Check
The User-Agent check is applied for requests from crawlers and robots which declared their identity to the web server through the User-Agent field (SI robots). We excluded these robots by applying this heuristic before the calculations of the session features to avoid biasing the results.

Number of User-Agent per IP
As explained earlier (Section 4.4), we used 20 as a threshold for the maximum number of different User-Agents for each IP. Users with more than 20 different User-Agents were classified as robots.

Robots.txt file
Web site administrators put a list of access restrictions to specify which parts of their web site are not allowed to be visited by robots. We labeled the sessions in which users downloaded the robots.txt file for the Wayback Machine (http://web.archive.org/robots.txt) as robots.

Browsing Speed (BS)
The importance and the effect of BS has been discussed and used for detecting robots many times [20,28,22]. We use BS ≤ 0.5 (i.e., no faster than one request every two seconds) as a threshold for human browsing speed [4]. We observed that this threshold is appropriate for our dataset, so we classify the sessions with BS > 0.5 as robots.

Image-to-HTML Ratio (IH)
Human sessions should have more images than robot sessions because of the embedded images present in most HTML pages. Robots tend to retrieve only HTML pages, while ignoring image formats. We used the IH metric calculated previously for each session to detect robots. In [26], 1:10 IH had been suggested as a good threshold for distinguishing robots from humans. We label a session with less than one image file for every 10 HTML files as a robot. IH is the only heuristic that does not require a session have at least two requests. This heuristic is the best predictor for robots [27,26], and it has a strong effect on our dataset.

RESULTS AND ANALYSIS
In this section, we explain the results of preprocessing the dataset (described in Sections 4.3-4.5) and of applying the heuristics for robot detection (described in Section 4.6). We analyze the resulting data and contrast the behavior and access patterns of humans and robots. We conclude with an analysis of the temporal preference of human users.

Traffic Analysis
To extract the user access patterns for web archives from the Wayback access logs, we first applied data preprocessing techniques (data cleaning, user identification, session identification) to convert the log file into web server sessions. The raw log file contains 2M requests from which we determined 21,932 unique IPs. Because of the stateless nature of the log files, we identified the users based on the IP and User-Agent to identify 33,841 users who created 37,634 different sessions.
The characteristics of each filter (3xx status code, embedded resources, static resources and liveweb, invalid requests, HEAD) and the total number of excluded requests after applying all the filters together are shown in Table 3. The number of records in the Feb. 2 sample was decreased from 2M to 426,317 (21.3% of the requests in the raw file). Table 2 contains the results of applying the heuristics for detecting robots. The rules are not mutually exclusive, but we calculated the number of requests which had been labeled as robots from each filter separately. IH had the largest effect on detecting robots. We used a 1:10 IH as a threshold for distinguishing robots from humans. We found that 99.93% of the sessions which were detected by this heuristic had 0 images. BS is also important, because it classified a significant number of robots who had a BS (more than 0.5 requests/second) impossible for humans.   the percentage of raw requests from humans and robots did not equal 2M requests. The reason is that there are many accesses that were created by invalid requests to the web server. Furthermore, there are many requests to embedded resources only, which were filtered. The percentage of human requests after cleaning and separating robot requests is only 1.5% of the 2M requests. The significant discovery here is the 10:1 ratio of robot sessions to human sessions. This ratio is a strong motivation for building an API interface that serves robot accesses in order to decrease the load of robots on the Wayback Machine. A typical human session costs more than a robot session as humans average 1.30 MB/session and robots average 0.58 MB/session. Human requests include automatic downloads of the embedded resources of the web pages they access, and robots usually ignore downloading these embedded resources.

Robots vs Humans
We discovered that most of the robots had a breadth search strategy in downloading the web pages from the Wayback Machine; more than 95% of the robots downloaded TimeMaps only, as shown in Table 4. On the other hand, of all human requests, only 18.5% were for TimeMaps.

Session Length (S l )
After detecting the robots, we separated them from humans and analyzed their behaviors individually. Figure 7 shows the session length frequency for robots in red and for humans in blue. We notice from the figure that many more robots have longer sessions than humans. TheS l for robots is 10 requests/session, while humans have anS l of 9 requests/session.

Session Duration (S d )
We computed session duration by subtracting the time of the first request from the time of the last request for each session. Session duration requires at least two requests. Figure 8 shows the percentage of sessions with different session durations for robots and humans. We can see that the majority of the sessions were short, taking into consideration that we did not count the time spent on the last requested web page. TheS d is 10 minutes for robots and 5 minutes for humans.

Inter-Request Time
We also calculatedSrt and stdev(Srt) for each session. We found that the median values ofSrt for human and robot sessions are 19 seconds and 40 seconds, respectively. The median of stdev(Srt) values is 37 seconds for robots and 11 seconds for humans. This indicates that robots tend to have more irregular periods between HTML requests than humans, and this matches the finding by Tan et al. [27].

Web Archive User Access Patterns
How do users go through web archives? Do they go in deeply from URI-R1 to URI-R2, do they browse broadly from URI-M1 to URI-M2 for the same URI-R, or do they use a combination of these two patterns? Are robot accesses similar to human accesses?
In this section, we answer the previous questions by extracting the user access patterns for web archives from our filtered dataset. The requested URIs for each session were extracted and then identified based on their type, URI-M or URI-T. We also extracted the URI-R of each requested URI to compare it with the other URI-Rs from the same session. Because of the existence of different forms of URIs which refer to the same website [18], we applied URI canonicalization for the URI-Rs to normalize them under one host [8].
We discovered four basic building blocks (Dip, Slide, Dive, Skim) of the user access patterns for web archives.

Dip
Dip is the pattern where the user requests a single URI. This URI can be a URI-M or a URI-T. It represents the most repeated pattern for humans (33% of all sessions) and robots (49% of all sessions). URI-Ms contribute to 83% of human sessions that exhibit the Dip pattern, although 94% of the robot Dips are requests for URI-Ts.

Slide
The user who is interested in travelling through time, browsing different copies of the same URI-R, creates the Slide pattern. There are only a few humans who access the web archives broadly then navigate away (4.2% of all sessions). Robot sessions do not have this pattern with a noticeable percentage (0.1% of all sessions).

Dive
Dive represents the second highest percentage of human sessions, 29.7%. In this pattern, the user goes deeply for browsing hyperlinks of URI-Ms. The robot sessions which were composed of this pattern crawl the web sites deeply, but they are not a significant number of sessions.

Skim
Skim is the pattern for which the users access different numbers of TimeMaps. Robot sessions exhibit this pattern 48.7% of the time. Investigating the relationship between the topics of the URI-Rs of the requested TimeMaps during a single session is one of our goals for upcoming research.

User
Pattern

Pattern Length
Each pattern is made up of a number of requests, which we call the pattern length. We calculated the pattern length for all sessions. The median, mean, and standard deviation of the lengths of each pattern for robots and humans are summarized in Table 5. For humans, the longest mean pattern length is an 8-request Dive, while for robots the longest mean pattern length is 21 requests in a Skim. Figure 10 shows both the unique and total number of mementos referenced grouped by the year of their Memento-Datetime. Although there is no clear temporal preference for any one year of the unique mementos, there were a significant number of repeated requests for mementos from 2011. This locality of reference suggests that there is an important benefit to be gained by caching the mementos from the recent past. Figure 11 shows that the total number of mementos available for 2011 was similar to previous years. In both Figures 11 and 10, pre-2001 data is included although in those years the archives are too sparse for meaningful comparison with later years.

CONCLUSIONS AND FUTURE WORK
We introduced the basic building blocks (Dip, Slide, Dive, and Skim) for user access patterns for web archives through an analysis of the Internet Archive's Wayback Machine access logs. We applied heuristics for detecting robots and found that robot sessions outnumber human sessions 10:1. This suggests that there is utility in building an API interface that serves robot accesses. Robots account for 91% of sessions and 93% of requests to the Wayback Machine, yet robots outnumber humans 5:4 only in terms of raw, unfiltered requests and 4:1 in terms of megabytes transferred. We found that humans download more information per session due to embedded resources, which robots ignore. We also analyzed human and robot access patterns to emphasize the similarities and the differences between them. We found that robots mainly exhibit the Dip and Skim patterns, with about 49% of their sessions for each pattern, and that they access TimeMaps almost exclusively. Humans exhibit the Dip and Dive patterns the most with 39% and 30% of their sessions, respectively. Unlike robots, humans mainly access archived pages rather than TimeMaps. Finally, we provide an analysis for the temporal preferences of humans based on the Memento-Datetime (by year) of their requests and discovered significant repetitions for requests in 2011. This suggests that there is a benefit to be gained by caching mementos from the recent past.
Web server logs are a rich source for information about web archives. We are planning to extend our analysis to serve other applications of web usage mining, such as personalization for making dynamic recommendations to web archive users based on their navigational behavior patterns by using data mining techniques. Further, we will study the validity of applying searching and browsing models for the current web to web archives. We also expect that Slides and Dives that users create on web archives may create stories around a particular event. We plan to extend our study on a large data set to detect stories that humans might create from their access patterns, which will be integrated into the live web to produce automatic stories about specific event for the users.

ACKNOWLEDGMENTS
This work was supported in part by the NSF (IIS 1009392) and the Library of Congress. We thank Kris Carpenter Negulescu (Internet Archive) for access to the anonymized Wayback Machine logs.