This clearly written and well-researched paper deals with sequential searching of what it calls a “list” (an ordered set K={k1, . . . , kN} of keys ki), where after each successful search for a key kj, 1≤Cj≤CN, the keys are reordered dynamically according to a heuristic rule R. In particular, the rules considered are:
:CR:A=:CTTranspose kj and kj−1, j>1.
R=M: Move kj to the first position of K.
R=C: Update a frequency-of-search count for kj, and move kj so as to maintain the keys in descending order of count.
The “best” rule will be the one that minimizes the “cost” (number of comparisons required) for the search. Traditionally, the asymptotic expected cost AR of a single search has been estimated: it turns out that AT≤M and that AC is small, thus encouraging the use of rule T in preference to rule M and the use of rule C when storage is available for counts. In this paper, the authors employ a new nonprobabilistic approach: the total cost CR=CR(S) of searches on all keys in a given request sequence S is used as the criterion for rule selection. They show that on this basis CM and CC are small for any sequence S, while CT may become large. In contrast to the established approach, then, these theoretical results encourage the use of rule M, a conclusion reinforced by empirical tests devised by the authors.
The heart of the authors’ theoretical results is the concept of pairwise independence in the sequence S: a rule R has the Pairwise Independence Property (PIP) if, for every request sequence S, the number of comparisons of a particular key kj&egr;S against another particular key kh&egr;S is independent (using rule R) of all other keys in S. It seems then to be true (though the authors do not explicitly state this generalization of their results) that a sufficient condition for CR to be “small” is that R have PIP. Further, it would have been of interest if the authors had addressed the question of whether or not this condition is also necessary. Finally, in their empirical tests, the authors use key lists K which are initially empty, then gradually updated by unsuccessful searches. It would have been interesting to see what, if any, qualitative differences would have been introduced into the test results by using lists which initially already contained all the keys in some arbitrary order.
