Information-Theoretic Methods for Prediction in the Wireless and Wired Web

Introduction

The proliferation of wireless cellular networks and the penetration of Internet services are changing many aspects of Web computing. Constantly increasing client populations utilize diverse devices to access the wired and wireless medium, and various heterogeneous applications (e.g., traffic- and weather-condition broadcasting, streaming video) are being developed to satisfy the eager requirements of the clients. In this environment, seamless and ubiquitous connectivity as well as low client-perceived latencies are two fundamental goals. The first goal calls for smart techniques for determining the current and future location of a mobile node, and the second goal calls for efficient and effective techniques for deducing future client requests for information pieces.

Both of the aforementioned problems are related to the ability of the underlying network to record, learn, and subsequently predict the mobile user’s behavior, that is, its movements or its information needs. The success of the prediction is presupposed and is boosted by the fact that mobile users exhibit some degree of regularity in their movement and/or in their access patterns (Bhattacharya & Das, 2002; Nanopoulos, Katsaros, & Manolopoulos, 2003). This regularity may be apparent in the behavior of each individual client or in client groups. The detection of regularity patterns can lead to drastic improvements on the underlying wireless network’s performance. Accurate data-request prediction results in effective data prefetching (Nanopoulos et al., 2003) combined with a caching mechanism (Katsaros & Manolopoulos, 2004; Vakali, 2001) can reduce user-perceived latencies as well as server and network loads. Also, effective solutions to the mobility tracking and prediction problem can reduce the update and paging costs, freeing the network from excessive signaling traffic (Bhattacharya & Das, 2002).

These issues had been treated in isolation, but pioneering works (Bhattacharya & Das, 2002; Vitter & Krishnan, 1996) are paving the way for treating both problems in a homogeneous fashion. They exhibited the possibility of using methods that have traditionally been used for data compression (thus characterized as information-theoretic) in carrying out prediction. The unifying principle is that they model the respective state space as finite alphabets comprised of discrete symbols. In the mobility tracking scenario, the alphabet consists of all possible sites (cells) where the client has ever visited or might visit (assuming that the number of cells in the coverage area is finite). In the request-prediction scenario, the alphabet consists of all the data objects requested by the client plus the objects that might be requested in the future (assuming that the objects come from a database and thus their number is finite).

A smart network can record the movement (request) history and then construct a mobility (data-access) model for its clients. The history refers to the past, but the model is probabilistic and extends to the future. As uncertainty is inherent in mobile movements or requests, we can consider the requests to be the outcome of an underlying stochastic process, which can be modeled using established information-theoretic concepts and tools (Misra, Roy, & Das, 2004; Vitter & Krishnan, 1996).

In our earlier work, reported in Nanopoulos et al. (2003), we described a framework that was able to embrace some algorithms that had been presented in the context of Web prefetching. That framework was able to present those algorithms as variations of the standard PPM (prediction by partial match) technique. The emphasis of the framework was on differentiating between the techniques based on whether they record contiguous subsequences or noncontiguous subsequences. From that work, it was clear that the discovery of noncontiguous subsequences required considerable computational effort and could be realized only through off-line algorithms.