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)?

  • 3
    $\begingroup$ this is rather broad: one variant of this is a classic online setting. another variant would be online learning from distributional data. So a short answer is YES, it has been extensively studied. $\endgroup$ Feb 26, 2011 at 3:48
  • 1
    $\begingroup$ I will suggest points I think that would improve your answer, without downvoting: Instead of having an additional space requirement, require the algorithm to be streaming. If the best part of your interest in this question is the mentioned application (diary) , you should include this in the original question. Given this framework, we can use statistical knowledge to solve it easier (e.g. your sleep cycle is more predictable than a random string of symbols). As @Suresh Venkat notes, given your choices, you can find a lot of material on these problems. $\endgroup$
    – chazisop
    Feb 26, 2011 at 4:10
  • $\begingroup$ Thanks chazisop. I tried to make the question more specific, in particular adding the space requirement. I don't know how to express formally the time hints. What would be a good set of terms ("online learning" brought too many other things)? $\endgroup$
    – J..y B..y
    Feb 26, 2011 at 4:22

1 Answer 1


While I'm still not entirely sure what you're looking for, you might try reading Avrim Blum's talk on Online Learning and Prediction, and that might help you focus on areas of interest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.