Parallel Search in Matrices with Sorted ColumnsProceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing (1995)
In this paper we consider searching, and also ranking, in an m x 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  paper on sequential unbounded searching to parallel searching in matrices, which surprisingly leads to an asymptotic improvement.
- parallel algorithms,
Publication DateOctober 25, 1995
Citation InformationAmit Jain. "Parallel Search in Matrices with Sorted Columns" Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing (1995)
Available at: http://works.bepress.com/amit_jain/3/