An optimal absorbing list organization strategy with constant memory requirements (Q688166)

Let \({\mathfrak R}=\{R_ 1,\ldots,R_ N\}\) be a list of elements where \(R_ i\) is accessed with a probability \(s_ i\). The vector \([s_ 1,s_ 2,\ldots,s_ N]^ T\) (whose components sum to unity) is represented by \({\mathfrak S}\), and is called the user's query distribution. \({\mathfrak S}\) is assumed to stationary but unknown. In order to minimize the average retrieval cost the elements must be arranged in the descending order of \(\{s_ i\}\). Since \({\mathfrak S}\) is unknown a priori, in this paper, we shall attempt to render the list self-organizing so that the average access time is asymptotically minimized. Various ergodic adaptive strategies such as the \(\text{Move}_ - \text{To}_ -\text{Front}\) (MTF) Rule, the Transposition Rule, the \(\text{Move}_ -k_ -\text{Ahead}\) rule and the \(\text{POS}_ -k\) Rule have been described in the literature. The properties of these schemes are found in the respective references of the surveys [\textit{G. H. Gonnet}, \textit{J. I. Munro} and \textit{H. Suwanda}, Exegesis of self organizing linear search, SIAM J. Comput. 10, 613-637 (1981; Zbl 0461.68064); \textit{J. H. Hester} and \textit{D. S. Hirschberg}, Self- organizing linear search, ACM Comput. Surveys 17, 295-311 (1985)]. The literature reports only two stochastic absorbing list re-organizing methods [\textit{B. J. Oommen} and \textit{E. R. Hansen}, List organizing strategies using stochastic move-to-front and stochastic move-to-rear operations, SIAM J. Comput. 16, 705-716 (1987; Zbl 0654.68074)] and the following deterministic absorbing schemes both of which are of a \(\text{Move}_ -\text{To}_ -\text{Rear}\) (MTR) flavour [\textit{B. J. Oommen}, \textit{E. R. Hansen} and \textit{J. I. Munro}, Deterministic optimal and expedient move-to-rear list organizing strategies, Theoret. Comput. Sci. 74, 183-197 (1990; Zbl 0701.68041)]: (i) A deterministic linear-space MTR rule which moves the accessed element to the rear of the list if it has been accessed \(k\) times. The scheme is asymptotically optimal. It performs \(N\) reorganization operations. (ii) A deterministic constant-space MTR rule which moves the accessed element to the rear of the list if it has been accessed \(k\) consecutive times. This scheme was proven to be expedient [\textit{B. J. Oommen}, \textit{E. R. Hansen} and \textit{J. I. Munro}, 1990, loc. cit.]. This communication describes an improved version of the latter scheme. We shall later show that the scheme can be viewed as a MTF strategy in which the ``Front'' of the list is dynamically updated.