Adaptive linear list reorganization under a generalized query system
Radhakrishna S. Valiveti, B. John Oommen, J.R. Zgierski · Journal of Applied Probability · 1995
We consider the problem of reorganizing a linear list, when the individual queries consist of accesses to a subset of the elements stored, as opposed to the individual elements themselves. In this paper, which to our knowledge represents the first reported result in this model of query processing, we first propose a simple model for a query generator which emits set queries. Subsequently, we present extensions to the classical move-to-front (MTF) and transposition (TR) rules under this generalized query generation mechanism and analyze their performance.