Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-19T23:53:37.458Z Has data issue: false hasContentIssue false
  • English
  • Français

The performance of the move-to-front scheme under some particular forms of Markov requests

Part of: Theory of data Computer system organization Markov processes

Published online by Cambridge University Press:  14 July 2016

Eliane R. Rodrigues
Eliane R. Rodrigues*
Affiliation:
Universidade de Brasília
*
∗Present address: Instituto de Matemáticas, UNAM, Area de la Investigación Científica, Circuita Exterior, Ciudad Universitaria, México DF 04510, México.
Get access Rights & Permissions [Opens in a new window]

Abstract

The move-to-front scheme is studied taking into account some forms of Markov dependence for the way items are requested. One of the dependences specifically rules out two consecutive requests for the same item. The other is the so-called p-correlation. An expression for the stationary distribution of the sequence of arrangements of items is given in each case. A necessary and sufficient condition for these distributions to belong to a particular class of distributions is also given. The mean search time for an item is calculated for each form of dependence and these are compared with the value obtained in the case of independent requests. Some properties of the sequence of requests are given. Finally, an expression for the variance of the search time is obtained.

Keywords

MARKOV DEPENDENCEMEAN SEARCH TIMESTATIONARY DISTRIBUTIONVARIANCE OF THE SEARCH TIME

MSC classification

Primary: 60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Secondary: 68M20: Performance evaluation; queueing; scheduling 68P10: Searching and sorting
Type
Research Papers
Information
Journal of Applied Probability , Volume 32 , Issue 4 , December 1995 , pp. 1089 - 1102
Copyright
Copyright © Applied Probability Trust 1995 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Most of this work was done while the author was doing her Ph.D. at Queen Mary and Westfield College, University of London, UK.

References

Burville, P. J. and Kingman, J. F. C. (1973) On a model for storage and search. J. Appl. Prob. 10, 697–701.Google Scholar
Chassaing, P. (1992) Optimality of the move-to-front heuristic for self-organizing data structures. Preprint.Google Scholar
Chung, K. L. (1967) Markov Chains with Stationary Transition Probabilities, 2nd edn. Springer-Verlag, Berlin.Google Scholar
Dobrow, R. P. (1994) The move-to-root self-organizing trees with Markov dependent requests. Preprint.Google Scholar
Dobrow, R. P. and Fill, J. A. (1994) The move-to-front rule for self-organizing lists with Markov dependent requests. Preprint.Google Scholar
Hendricks, W. J. (1972) The stationary distribution of an interesting Markov chain. J. Appl. Prob. 9, 231–233.Google Scholar
Hendricks, W. J. (1976) An account of self-organizing schemes. SIAM J. Computing 5, 715–723.Google Scholar
Kemeny, J. G. and Snell, J. L. (1960) Finite Markov Chains. Van Nostrand, New York.Google Scholar
Kingman, J. F. C. (1975) Random discrete distributions. J. R. Statist. Soc. B37, 1–15.Google Scholar
Lam, K., Leung, M.-Y. and Siu, M.-K. (1984) Self-organizing files with dependent accesses. J. Appl. Prob. 21, 343–359.Google Scholar
McCabe, J. (1965) On serial files with relocatable records. Operat. Res. 13, 609–618.Google Scholar
Phatarfod, R. M. and Dyte, D. (1992) The linear search problem with Markov dependent requests. Preprint.Google Scholar
Rivest, R. (1976) On self-organizing sequential search heuristic. Commun. ACM 19, 63–67.Google Scholar
Valiveti, R. S. and Oommen, B. J. (1990) Adaptive list organizing for non-stationary query distributions. Part I: Move-to-front rule. Preprint.Google Scholar