A Markov model for web request prediction

Abstract

Increasing web content and Internet traffic is making web prediction models popular. A web prediction model helps to predict user requests ahead of time, making web servers more responsive. It caches these pages at the server side or pre-sends the response to the client to reduce web latency. Several prediction techniques have been tried in the past; Markov based prediction models being the most popular ones. Among these, the All-K[superscript]th -order Markov model has been found to be most effective. In this project, a Markov tree is designed, which is a fourth order model but behaves like an All-K[superscript]th-order Markov model because of its ability to recognize different order models according to the height of the tree. It has dual characteristics of good applicability and predictive accuracy. A Markov tree gives a complete description on the frequency with which a particular state occurs, and the number of times a path to a particular state is used, to access its child nodes. Further, the model can be pruned to eliminate states that have very little contribution towards the accuracy of the model.

In this work, an evolutionary model is designed that makes use of a fitness function. The fitness function is a weighted sum of precision and the extent of coverage that the model offers. This helps to generate a model with reduced complexity. Results indicate that this model performs consistently with good predictive accuracy among different log files. The evolutionary approach helps to train the model to make predictions commensurate to current web browsing patterns.