{'fraction_non_alphanumeric': 0.01687027341477603, 'fraction_numerical': 0.0, 'mean_word_length': 5.254545454545455, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online prediction algorithms for databases and operating systems

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 what event is going to happen in the future, when a specific event will take place, or 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 prefetching requires a prediction of which page is going to be next requested by a user. The problem of disk spindown in mobile machines, modeled by the 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 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.