Parallel Search and Multisearch in Matrices with Sorted Columns

In this paper we consider the problem of searching, and 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(lg m lg lg m)-time for small elements with rank k ≤ m and in O(lg m lg lg m lg (k/m))-time otherwise. Then we show how to improve the parallel-searching algorithm to run in O(lg m lg*lg m))-time with optimal work for small elements (with rank k ≤ m) and in O(lg m lg* (lg m) lg(k/m))-time with optimal work for large elements (m < k ≤ mn). Next we present a sequential algorithm for multisearch in a matrix with sorted columns. Finally we present a parallel multisearch algorithm that is a generalization of the sequential multisearch algorithm and has a nontrivial dependence on the ranks of the search-elements as well as on the number of search-elements.