Optimal associative searching on a cellular computer

摘要

The performance of the cellular computer proposed by Mego has been investigated by programming a number of associative search algorithms and analyzing the time and space required for their execution. The present work describes the results of three different analysis techniques applied to algorithms for nearest neighbor and closest pair problems for files of n points in k-dimensional space. >Brute force methods are described for solving the nearest neighbor problem. If the initial program expression is suitably placed in memory, analysis of the most parallel brute force algorithm yields complexity results of O(k) time and O(kn) space. These bounds are shown to be asymptotically optimal with respect to the problem and the machine. >Brute force, semi-parallel, and divide-and-conquer solutions are described for solving the closest pair problem. Analyses of the best semi-parallel algorithms yield complexity results of O(kn) time and space, which are shown to be asymptotically optimal.