This paper discusses the PROMISE (Predicting User Behavior in Multidimensional Information System Environments) approach, that deploys information about characteristic patterns in the user’s multidimensional data access in order to improve caching algorithms of OLAP systems. The paper motivates this approach by presenting results of an analysis of the user behavior in a real-world OLAP environment. Further contributions of this paper are a model for characteristic OLAP query patterns based on Markov Models and a corresponding OLAP query prediction algorithm.