Carleton University
Technical Report TR-97-07
May 1997
TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps *
Abstract
t-A common drawback to all the reported self-organizing sequeI_!.tial search algorithms is that they all fail to consider the size of the list when reorganizing it. The two extremes are the well-known and most commonly analyzed algorithms, the move-to-front rule and the transposition rule. This paper presents two new memoryfree self-organizing sequential search algorithms, both of which overcome this drawback. The first algorithm is called swap-with-parent (SWP) and the second is called move-to-parent (MTP). Under the swap-with-parent heuristic, the accessed record is exchanged with its “parent” ( considering the list as a heap structure with no ordering constraints between parents and their children) and all the other records are untouched. whereas under the move-to-parent heuristic, the accessed record is moved to its parent’s positions and all the records in between get shifted back one position. It is shown that under the SWP heuristic, the Markov chain representing the scheme is time reversible. This property allows us to derive its asymptotic equilibrium probabilities a rather complicated expression for its average search cost. We conjecture that it costs no more than the move-to-front rule and its convergence is intermediate to the move-to-front rule and the transposition rule. For the performance of the move-to-parent rule, empirical comparison shows that it lies between the move-to-front heuristic and the transposition heuristic, and that it is better than the swap-with-parent rule.