Carleton University
Technical Report TR-97-08
May 1997
TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists *
Abstract
Self organizing linear search algorithms have been in the literature for almost 30 years, and numerous schemes have been proposed during that time. Among all the previous algorithms, the move-to-front rule and the transposition rule are the most extensively analyzed schemes. Recently we have proposed and thoroughly analyzed a new scheme, the swap-with-parent rule, which views the list as a heap structure with no ordering constraints between parents and their children {15}. From the analyses of the transposition rule and the swap-with-parent rule, it can be seen that the fundamental property of the corresponding Markov chain being time reversible greatly simplifies the analysis of the algorithm. In this paper, we shall show the existence of a class of time reversible Markov chains resulting from performing swaps on “implicit” tree structures (called ss_trees) which generalize and extend the results concerning the transposition heuristic and the swap-with-parent heuristic.
This paper introduces a generalization of the transposition rule and the swapwith-parent rule – the swap-with-parent-in-an-ss_tree heuristic and its modification the move-to-parent-in-an-ss_tree heuristic. Detailed expressions for the asymptotic probabilities and the asymptotic search cost of the scheme have been derived.