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.
PDF