Self-organizing files with dependent accesses

Abstract

We analyze certain self-organizing filing techniques when accesses are assumed to be dependent on each other. The stream of requests for accessing records in a file is modelled as a Markov chain. A general framework is introduced to obtain the asymptotic search cost of a memory-free self-organizing heuristic. The move-to-front heuristic is studied in detail. A formula for the asymptotic search cost, which generalizes that in the case of independent accesses, is obtained. Numerical examples on the performance of the transposition heuristic are provided, and compared with that of the move-to-front heuristic.