Parallel search in matrices with sorted columns
A. Jain · 2002
In this paper we consider searching, and also ranking, in an m/spl times/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/spl les/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 J.L. Bentley and A.C. Yao's (1976) paper on sequential unbounded searching to parallel searching in matrices, which surprisingly leads to an asymptotic improvement.