Consider the following online problem:
For $\sigma$ and $k$ fixed, given a string of symbols from alphabet $[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the next symbol belongs in $S$, in space independent of the length of the past string.
This problem is similar to online cache management in the sense that failing the guess is a miss, while guessing correctly is a catch. It is much more general than cache management in the sense that symbols can be added to (the cache) $S$ without having generated a miss, just based on correlations previously learned (e.g. $b$ always follows $a$). It presents the same problem of analysis (competitive analysis and the like) than other online problems in the sense that the worst case is intractable while some good performance can be expected on practical instances.
It could have application to caching with pre-fetching. I thought of it while thinking about the dream specs of a diary application on a smart phone (i.e. reduced screen and costly typing), which given the past submissions of the user (went to bed, woke up, ate eggs, took the bus, etc...) must suggest on the screen $k$ activities to be logged next, a menu for others and a field to enter a new one (using the menu is a miss, writing a new one is unavoidable for any solution). In this case one should consider the space taken by the algorithm: remembering the whole section of previous queries is not an option, only a finite, lossy (ditching outliers) summary of it. One could give additional information to the guesser such as the time of the day, but I do not know how to fit it nicely in the theoretical model.
Was such a problem or a variant already studied? Under which name? Using which model (Dorrigiv and Lopez-Ortiz "cooperative" analysis comes to mind)?