On Ordered Retrieval from an Associative Memory [Letter to the Editor]
LC Johnson, M. H. McAndrew · IBM Journal of Research and Development · 1964
In a recent issue of this Journal, Seeber and Lindquist1describe an algorithm for ordered retrieval of the items stored in an associative memory. The basic method employs one or more memory interrogations per item retrieved. In discussing the average number of interrogations per item required for the case of N random binary numbers, they employ a formulation that is difficult to evaluate for large numbers and large N. The main purpose of this Communication is to extend their analysis for the case when N is large; toward this end, it is instructive and interesting in itself to generalize the algorithm for an arbitrary radix r, where r ≥ 2. The presentation is in two parts. The first reviews the algorithm, exhibits a small example for numbers in a radix 4 representation, outlines the analytical approach, and comments on the nature of the results. The second presents a mathematical justification of the results.