{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T13:33:15Z","timestamp":1713015195971},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1999,12]]},"abstract":"<jats:p> In this paper we consider the problem of searching, and ranking, in an m \u00d7 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 \u2264 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 <jats:sup>*<\/jats:sup> lg m))-time with optimal work for small elements (with rank k \u2264 m) and in O( lg m lg <jats:sup>*<\/jats:sup> ( lg m) lg (k\/m))-time with optimal work for large elements (m &lt; k \u2264 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. <\/jats:p>","DOI":"10.1142\/s0129626499000530","type":"journal-article","created":{"date-parts":[[2003,4,25]],"date-time":"2003-04-25T13:10:49Z","timestamp":1051276249000},"page":"575-586","source":"Crossref","is-referenced-by-count":1,"title":["PARALLEL SEARCH AND MULTISEARCH IN MATRICES WITH SORTED COLUMNS"],"prefix":"10.1142","volume":"09","author":[{"given":"AMIT","family":"JAIN","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Boise State University, Boise, Idaho 83725, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90071-5"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/0218014"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90019-X"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1137\/0217009"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00009-3"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90048-4"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90035-4"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0098"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90138-5"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1137\/0207013"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626499000530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:20:14Z","timestamp":1565108414000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626499000530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,12]]},"references-count":12,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1999,12]]}},"alternative-id":["10.1142\/S0129626499000530"],"URL":"https:\/\/doi.org\/10.1142\/s0129626499000530","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,12]]}}}