Self-Organizing Data Structures with Dependent Accesses

摘要

We consider self-organizing data structures in the case where the sequence of accesses can be modeled by a first order Markov chain. For the simple-k-and batched-k-move-to-front schemes, explicit formulae for the expected search costs are derived and ocmpared. We use a new approach that employs the technique of expanding a Markov chain. This approach generalizes the results of Gonnet/Munro/Suwanda. In order to analyze arbitrary memory-free move-forward heuristics for linear lists, we restrict our attention to a special access sequence, thereby reducing the state space of the chain governign the behaviour of the data structure. In the case of accesses with locality, we find that the hierarchies of self-organizing data structures with respect to the expected search time are reversed, compared with independent accesses. Finally we look at self-organizing binary trees with the move-to-root rule and compare the expected search cost with the entropy of the Markov chain of accesses.