The Computer Journal Advance Access originally published online on December 15, 2006
The Computer Journal 2007 50(2):186-196; doi:10.1093/comjnl/bxl067
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A Novel Framework for Self-Organizing Lists in Environments with Locality of Reference: Lists-on-Lists
1 School of Computer Science, Carleton University, Ottawa, Canada KIS 5B6
2 Adjunct Professor with the Department of Information and Communication Technology, Agder University College in Grimstad, Norway
* Corresponding author: oommen{at}scs.carleton.ca
Received 11 April 2006; revised 10 October 2006
We examine the problem of self-organizing linear search lists, which are lists that react to queries received from an environment by running a heuristic to reorganize the records in order to minimize the search cost. In particular, we are concerned with 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. An 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 a learning automaton-based partitioning algorithm, we demonstrate that we can accurately classify the different contexts of the sublist. To the best of our knowledge, both the concept of reorganizing the list ‘hierarchically’ using such a two-step LOL process, and the application of stochastic learning to this problem are new to the field. Indeed, while the costs involved to achieve these enhancements are almost of the same order as that which achieves basic list-organizing, using this framework, we were able to empirically achieve asymptotic search costs that are significantly superior to (sometimes even an order of magnitude better than) the Move-To-Front heuristic, widely acknowledged as the best algorithm for such environments.
Key Words: Lists-on-Lists • adaptive data structures • self-organizing lists • locality of reference