ADAPTIVE LINEAR LIST REORGANIZATION UNDER A GENERALIZED QUERY SYSTEM

We consider the problem of reorganizing a linear list, when the indivi dual queries consist of accesses to a subset of the elements stored, a s 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 generat or 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.