Parallel search in matrices with sorted columns

In this paper we consider searching, and also ranking, in an m × n matrix with sorted columns on the EREW PRAM model. We propose a work-optimal parallel algorithm, based on the technique of accelerated cascading, that runs in O(log m log log m)-time for small elements with rank k ≤ m and in O(log m log log m log(k/m))-time otherwise. 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 [2] paper on sequential unbounded searching to parallel searching in matrices, which surprisingly leads to an asymptotic improvement.