Exegesis of Self-Organizing Linear Search

Abstract

We consider techniques for self-organizing linear search, examining the behavior of methods under arbitrary and specific probability distributions. The notion of moving an element forward after it has been accessed k times in a row is introduced. One implementation performs the transformation after any k identical requests. A second essentially groups requests into batches of k, and performs the action only if all requests of a batch are the same. Adopting as the transformation, the move to front heuristic, the second approach is shown in general to be superior. We show that the batched approach, with $k = 2$, leads to an average search time no greater than 1.21... times that of the optimal ordering. For the more direct approach, a ratio of 1.36... is shown under the same constraints. The simple move to front heuristic (i.e., $k = 1$) is also examined. It is shown that for a particular distribution this scheme can lead to an average number of probes $\pi/2$ times that of the optimal order. Within an interesting class of distributions, this is shown to be the worst average behavior.