On the competitive theory and practice of online list accessing algorithms

This paper concerns the online list accessing problem. In the first part of the paper we present two new families of list accessing algorithms. The fi rst family is of optimal, 2-competitive, deterministic online algorithms. T his family, called the MRI (MOVE-TO-RECENT-ITEM) family, includes as member s the well-known MOVE-TO-FRONT (MTF) algorithm and the recent, more "conser vative" algorithm TIMESTAMP due to Albers. So far MOVE-TO-FRONT and TIMESTA MP were the only algorithms known to be optimal in terms of their competiti ve ratio. This new family contains a sequence of algorithms {A(i)}(i greate r than or equal to1) where A(1) is equivalent to TIMESTAMP and the limit el ement A (oo) is MTF. Further, in this class, for each i, the algorithm A (i ) is more conservative than algorithm A (i + 1) in the sense that it is mor e reluctant to move an accessed item to the front, thus giving a gradual tr ansition from the conservative TIMESTAMP to the "reckless" MTF. The second new family, called the PRI (PASS-RECENT-ITEM) family, is also infinite and contains TIMESTAMP. We show that most algorithms in this family attain a co mpetitive ratio of 3. In the second, experimental, part of the paper we report the results of an extensive empirical study of the performances of a large set of online list accessing algorithms (including members of our MRI and PPI families). The algorithms' access cost performances were tested with respect to a number o f different request sequences. These include sequences of independent reque sts generated by probability distributions and sequences generated by Marko v sources to examine the influence of locality. It turns out that the degre e of locality has a considerable influence on the algorithms' absolute and relative. costs, as well as on their rankings. In another experiment we tes ted the algorithms' performances as data compressors in two variants of the compression scheme of Bentley et al. In both experiments, members of the M RI and PRI families were found to be among the best performing algorithms.