Adaptive linear list reorganization for a system processing set queries

The problem of reorganizing a linear list, when the individual records are accessed independently, 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 accesses are statistically dependent. Throughout this paper, the set accesses are processed by serializing the set elements.