Self-organizing search lists using probabilistic back-pointers

Reviewer: Theodore David Brown

Self-organizing search lists are linearly linked lists in which more frequently accessed records are moved forward. The literature has discussed the move to front, which approaches steady state quickly; the transpose, in which the record only moves ahead one record, which has a slower convergence rate but a smaller average cost per record access once steady state is reached; and move ahead k, which is a compromise. The authors first meld and generalize these record manipulation techniques into one algorithm by using a Boolean jump function that is evaluated at each probe. If jump is set to true, a back pointer b is set to the position of the current record. Once the requested key is found it is reinserted in front of the record that b points to. The authors point out that when reinsertions are done at fixed distances, as in the three techniques above, cost analyses are difficult. This is because the cumulative effect of reinsertions makes the distance searched non-independent. This leads them to suggest a probabilistic jump distance function. The major benefit as I see it is to allow analysis, not to improve performance.