Tech Report CS-95-24

Online Prediction Algorithms for Databases and Operating Systems

P. Krishnan

August 1995

Abstract:

In making online decisions, computer systems are inherently trying to predict future events. Typical decision problems in computer systems translate to three prediction scenarios: predicting {\em what\/} event is going to happen in the future, {\em when\/} a specific event will take place, or {\em how much\/} of something is going to happen. In this thesis, we develop practical algorithms for specific instances of these three prediction scenarios, and prove the goodness of our algorithms via analytical and experimental methods.

We study each of the three prediction scenarios via motivating systems problems. The problem of {\em prefetching\/} requires a prediction of which page is going to be next requested by a user. The problem of {\em disk spindown in mobile machines}, modeled by the {\em rent-to-buy\/} framework, requires an estimate of when the next disk access is going to happen. Query optimizers choose a database access strategy by predicting or estimating {\em selectivity}, i.e., by estimating the size of a query result.

We analyze the novel idea of using data compression techniques for prediction, and investigate the similarities and differences between the different prediction scenarios. We show the theoretical optimality and practical merit of prefetchers based on data compressors, study predictive and adaptive disk spindown strategies, and develop methods for estimating alphanumeric selectivity in relational databases. In each of our prediction algorithms, we cope with the stringent limits on the storage and time available to do prediction that are imposed by system environments. We conclude that good and practical predictors can be obtained from data compressors.

(complete text in pdf or gzipped postscript)