Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities (Q1305419)

Efficient information retrieval, data search, and self-organizing lists are studied. A complete asymptotic characterization of the move-to-front search cost distribution function or equivalently, the least-recently used caching fault probability is obtained for both heavy and light tails. In both cases the tail of the move-to-front search cost distribution is asymptotically directly proportional to the tail of the request distribution with an explicitly computable constant of proportionality. Formulas are obtained for the least-recently used caching probability. Simulation experiments using a C++ language are described.