Self-organizing linear search

Reviewer: Don Goelman

This paper is indeed of the survey genre. As might be expected, it does not demand a great deal of background; it is accessible to readers with some knowledge of data structures, particularly lists, and of the sequential search algorithm. It should be of interest not only to scholars seeking a summary of the history and results concerning the problem of self-organizing sequential search. Examples are also provided of practical contexts, particularly compiler construction, where the results are of some importance. The setting for this problem is the maintenance of a linear list which will undergo repeated searches. These searches will be done sequentially from the beginning of the list. In order to improve the behavior of these searches, the list is periodically reorganized in the hope that we can identify keys which are most frequently in demand, and, usually by moving them forward in the list, reduce the time needed to find them in future requests. The authors of this paper do an admirable job of describing the known algorithms for reorganizing the list, and covering the somewhat orthogonal topic of what measures are used in evaluating the algorithms. There is also a section on open problems in the field. The historical heuristics that are discussed include the big three: move-to-front, transpose, and count. The move-to-front algorithm moves the found record to the front of the list, maintaining the relative positions of the other list elements. Transpose switches the found record with its predecessor, if it has one. Finally, the count strategy includes in each record a field which contains the number of times its key has been requested. At each request, a record is moved forward enough positions to keep the list sorted in descending order by count. Besides these heuristics, the authors describe various meta-algorithms, hybrids, stochastic strategies, and their own JUMP algorithm. As for measures of complexity, the three important metrics are discussed. First, the average or asymptotic cost of a heuristic is the limiting search cost (measured generally in terms of comparisons, but the reorganization cost may also be included) for a single key; this assumes that each key is requested with a particular probability (the value of which is not known to the user). The second measure is the rate at which the search cost converges to its asymptotic value. The third metric is the amortized cost of a sequence of requests, where the list is being reorganized by the heuristic being measured. There are quite a few tradeoffs here, with transpose known often to have a lower asymptotic cost than move-to-front, but with move-to-front superior in its convergence rate and in its amortized cost. The style of this paper is quite readable, and the subject is presented in a very interesting fashion. However, the relative emphasis is too heavily weighted in favor of the asymptotic cost of an algorithm. As the authors of this paper point out, recent results by Bentley and McGeoch [1] and Sleator and Tarjan [2] show the superiority of the move-to-front algorithm (in some sense, even over the count heuristic [2]) in the amortized metric, and there is empirical evidence presented in [2] that this metric is the proper one to use.