Dynamic Memories with Faster Random and Sequential Access
by C.-K. Wong, D. T. Tang
This paper extends the dynamic memory proposed by Aho and Ullman in two directions. Instead of a shuffle permutation, block shuffles are introduced. By choosing suitable block sizes, faster random and sequential access may result. Another direction of extension comes from the addition of a reverse cyclic permutation, which results in even faster random and sequential access. Analyses for both the worst and the average cases are given. Generalizations to arbitrary radices are also discussed.