Skip to main content
Parallel Search and Multisearch in Matrices with Sorted Columns
Parallel Processing Letters (1999)
  • Amit Jain, Boise State University
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.
  • parallel algorithms,
  • Search,
  • Multisearch,
Publication Date
December, 1999
Citation Information
Amit Jain. "Parallel Search and Multisearch in Matrices with Sorted Columns" Parallel Processing Letters Vol. 9 Iss. 4 (1999)
Available at: