Pre-sending Documents on the WWW: A Comparative Study

David W. Albrecht, Ingrid Zukerman, Ann E. NicholsonIJCAI 1999

Abstract

This study explores the application of decision theory to the problem of web document pre-sending (prefetching). By balancing the potential reduction in user latency against the costs of wasted bandwidth, the proposed decision-theoretic policy aims to optimize network resource usage while improving the user experience.

Introduction

In the late 1990s, the "World Wide Wait" was a significant barrier to web usability. Pre-sending documents—transferring data to a client's cache before an explicit request is made—offered a solution to reduce perceived latency. However, this technique introduces an uncertainty-bandwidth trade-off: pre-sending the wrong document wastes resources, while failing to pre-send a requested document forces the user to wait.

Traditional "naive" policies often pre-sent the most likely next document regardless of cost. This paper introduces a decision-theoretic approach that evaluates whether the expected reduction in wait time justifies the risk of bandwidth waste.

Methodology

The researchers developed a two-stage system to manage pre-sending:

1. Prediction Model (maxHybrid)

To predict user behavior, the authors employed a hybrid of four Markov models:

  • Time-based: Analyzes the most recent request.
  • Second-order Time: Analyzes the sequence of the last two requests.
  • Space-based: Considers links available on the current page.
  • Linked Space-Time: Combines structural and temporal data.

The maxHybrid model dynamically selects the predictor with the highest probability for any given state.

2. Decision-Theoretic Policy

The core innovation is a policy that calculates the Expected Immediate Benefit. It weighs the probability of a document request against the transmission time, the cost of user waiting time ($cps$), and the cost of bandwidth ($cpb$). A document is only pre-sent if the calculated benefit is positive, ensuring a more conservative and resource-efficient strategy than naive methods.

Dataset and Evaluation

The system was tested using 15 months of web server logs from Monash University. The primary analysis focused on a 50-day subset containing over 1 million requests from approximately 60,000 unique clients. The data was split into 80% for training and 20% for testing.

Key Results

The maxHybrid model demonstrated robust predictive capabilities. In scenarios accounting for client caching, the model achieved a recall of approximately 53%, successfully pre-sending over half of the documents eventually requested by users.

Recall performance of the prediction model across different cache scenarios.

The decision-theoretic policy proved superior to naive strategies, particularly in its ability to avoid "negative benefit." While naive policies often resulted in significant resource waste when wait costs were low, the decision-theoretic model remained efficient by opting not to pre-send when the risk outweighed the reward.

Average total benefit comparing decision-theoretic (d) and naive (n) policies.

Key findings include:

  • Efficiency: The system makes pre-send decisions in about 33 milliseconds, adding negligible overhead.
  • Cost Sensitivity: The naive policy only outperforms the decision-theoretic model when the penalty for waiting is extremely high. In most realistic scenarios, the conservative nature of the decision-theoretic approach is more beneficial.
  • Cache Impact: Accounting for "eventual benefit" (the utility of a document later in a session) significantly alters the optimal strategy compared to "immediate benefit" (the very next click).

Conclusion and Future Work

The decision-theoretic approach effectively addresses the uncertainty of user behavior on the web. Future research directions include extending the prediction horizon beyond a single step, incorporating document size into timing estimations, and exploring the pre-sending of document "bundles" to further optimize performance.

Summary updated

BibTeX
@inproceedings{albrecht1999pre,
  author = {David W. Albrecht and Ingrid Zukerman and Ann E. Nicholson},
  title = {{Pre-sending Documents on the WWW: A Comparative Study}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure