Abstract
In this paper we consider the problem of searching, and also the related problem of ranking, in an $m \times n$ matrix with sorted columns on the EREW PRAM model. The proposed parallel algorithms are sensitive to the rank $k$ of the search-element. We propose a work-optimal parallel algorithm that runs in $O(\log m \log\log m)$-time for small elements with rank $k \leq m$ and in $O(\log m \; \log\log m \; \log (k/m))$-time for elements with large rank. Our algorithm is based on the technique of accelerated cascading. Then we present a sequential algorithm for multisearch in a matrix with sorted columns as a prelude to a parallel algorithm for multisearch in a matrix with sorted columns. The sequential algorithm uses ideas from the parallel technique of chaining. The parallel multisearch algorithm follows this sequential algorithm and has a nontrivial dependence not only on the ranks of the search-elements but also on the number of search-elements. Finally we show how to adapt ideas from Bentley and Yao's~\cite{by:aoaus} paper on sequential unbounded searching to parallel searching in matrices with sorted columns, which surprisingly leads to an asymptotic improvement in the parallel search algorithm. The improved algorithm runs for small elements (with rank $k \leq m$) in $O(\log m \log^*(\log m))$-time with optimal work and for large elements in $O(\log m \log^*(\log m) \log (k/m))$-time with optimal work.}
Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing, pp. 224--230, 1995.
View the PostScript document.