Lists on Lists: A Framework for Self-organizing Lists in Environments with Locality of Reference

摘要

We examine the problem of self-organizing linear search lists in environments with the locality of reference phenomenon, when the queries exhibit a probabilistic dependence between themselves. We introduce a novel list organization framework that we call Lists on Lists (LOL), which regards the list as a set of sublists that are manageable in the same way that individual records are. A LOL organization involves a reorganization operation on the accessed record level, as well as another on the sublist which it belongs to (the record's context). We show that it is beneficial to consider the reorganization of the context together with the accessed record, since other records within the context are likely to be accessed in the near future. With the aid of an automaton-based partitioning algorithm, we demonstrate that we can accurately classify the different contexts of the sublist. Using this framework, we were able to empirically achieve asymptotic search costs that are significantly superior to the move-to-front heuristic, widely acknowledged as the best algorithm for such environments.