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.
['C. K. Wong', 'Donald T. Tang']
Dynamic memories with faster random and sequential access