TR-181: Adaptive Linear List Reorganization under a Generalized Query System

Abstract

The problem of reorganizing a linear list, when the individual records are accessed indepen­dently, has been well studied. In this paper, self-organizing linear list heuristics are examined under a more general query system which allows accesses to any subset of the list of elements. We propose a pragmatic model for the query generator, characterized by a set of parameters of size equal to the number of elements in the list. We derive the distribution of accesses to the individual records of the list, and show that these records are statistically dependent. Throughout this paper, the set accesses are processed by serializing the set elements.
We then present extensions to the classical Move-To-Front (MTF) and Transposition (TR) rules under this generalized query generation mechanism. The resulting heuristics are termed MTF _TQS and TR_TQS respectively. Under this query generation model, the opti­mal (static) list is shown to be one in which the elements are ordered in the descending order of the total probability of accessing the records. The expected cost under the MTF _TQS heuristic is shown to be no more than 1r /2 times the mean access cost for the optimal list. We also prove that MTF _TQS and TR_TQS are superior to the simpler reorganization scheme in which the classical MTF or TR heuristics (respectively) is employed in conjunction with the (serial) stream consisting of individual record accesses. Experimental results for these heuristics are also reported.