Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-25T13:31:42.196Z Has data issue: false hasContentIssue false
  • English
  • Français

Self-organizing files with dependent accesses

Published online by Cambridge University Press:  14 July 2016

Kin Lam ,
Ming-Ying Leung  and
Man-Keung Siu
Kin Lam*
Affiliation:
University of Hong Kong
Ming-Ying Leung*
Affiliation:
University of Hong Kong
Man-Keung Siu*
Affiliation:
University of Hong Kong
*
∗ Postal address: Department of Statistics, University of Hong Kong.
∗∗ Postal address: Department of Mathematics, University of Hong Kong.
∗∗ Postal address: Department of Mathematics, University of Hong Kong.
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

LINEAR SEARCHMOVE-TO-FRONT RULETRANSPOSITION RULE
Type
Research Papers
Information
Journal of Applied Probability , Volume 21 , Issue 2 , June 1984 , pp. 343 - 359
Copyright
Copyright © Applied Probability Trust 1984 

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.)

References

Anderson, E. J., Nash, P. and Weber, R. R. (1982) A counterexample to a conjecture on optimal list ordering. J. Appl. Prob. 19, 730–732.Google Scholar
Arnaud, J. P. (1977) Sur quelques problèmes concernant les librairies. Thèse de 3eme cycle, Université Paul Sabatier, Toulouse, France.Google Scholar
Bitner, J. R. (1979) Heuristics that dynamically organize data structures. SIAM. J. Comput. 8, 82–110.Google Scholar
Burville, P. J. and Kingman, J. F. C. (1973) On a model for storage and search. J. Appl. Prob. 10, 697–701.Google Scholar
Chung, K. L. (1967) Markov Chains with Stationary Transition Probabilities, 2nd edn. Springer-Verlag, Berlin.Google Scholar
Gonnet, G. H., Munro, J. I. and Suwanda, H. (1981) Exegesis of self-organizing linear search. SIAM. J. Comput. 10, 613–637.Google Scholar
Harris, T. E. (1952) First passage and recurrence distributions. Trans. Amer. Math. Soc. 73, 471–486.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 systems. SIAM. J. Comput. 5, 715–723.Google Scholar
Kan, Y. C. and Ross, S. M. (1980) Optimal list order under partial memory constraints. J. Appl. Prob. 17, 1004–1015.Google Scholar
Kemeny, J. G. and Snell, J. L. (1960) Finite Markov Chains. Van Nostrand, Princeton, NJ.Google Scholar
Knuth, D. E. (1973) The Art of Computer Programming, Searching and Sorting, Vol. III. Addison-Wesley, Don Mills, Ont. Google Scholar
Konnecker, L. K. and Varol, Y. L. (1981) A note on heuristics for dynamic organization of data structures. Information Processing Lett. 12(5), 213–216.CrossRefGoogle Scholar
Lam, K., Siu, M. K. and Yu, C. T. (1981) A generalized counter scheme. Theoret. Comput. Sci. 16, 271–278.Google Scholar
Mccabe, J. (1965) On serial files with relocatable records. Operat. Res. 12, 609–618.CrossRefGoogle Scholar
Nelson, P. R. (1982) The transposition replacement policy with a partial memory. J. Appl. Prob. 19, 733–736.Google Scholar
Phelps, R. I. and Thomas, L. C. (1980) On optimal performance in self-organizing paging algorithms. J. Informat. Optimization Sci. 1, 80–93.CrossRefGoogle Scholar
Rivest, R. (1976) On self-organizing sequential search heuristics. Comm. ACM 19, 63–67.CrossRefGoogle Scholar