{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T03:51:22Z","timestamp":1648957882178},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,2]]},"abstract":"<jats:p> The computational model on which the algorithms are developed is the array with reconfigurable optical buses (AROB). It integrates the advantages of both optical transmission and electronic computation. The main contributions of this paper are in designing several optimal and\/or optimal speed-up template matching algorithms with varying degrees of parallelism on the AROB model. For an N \u00d7 N digitized image and an M \u00d7 M template, when the domains of the image and the template are O( log N)-bit integers, we first design several basic operations for window broadcasting and rotation. Then based on these basic operations, three efficient and scalable algorithms for template matching are derived using various numbers of processors on a two-dimensional (2-D) or 3-D AROB. For 1 \u2264 r \u2264 N, 1 \u2264 p \u2264 M \u2264 q \u2264 N, one runs in [Formula: see text] time using r \u00d7 r processors, another runs in [Formula: see text], (resp. [Formula: see text]) time using pN \u00d7 pN\/ log M (resp. pN \u00d7 pN \u00d7 log N) processors, and the other runs in [Formula: see text] (resp. [Formula: see text]) time using pq \u00d7 pq\/ log M (or pq \u00d7 pqN \u00d7 log N) processors, respectively. The latter two algorithms can be tuned to run in O(1) time on a 2-D AROB. To the best of our knowledge, there are no algorithms which can reach this time complexity for this problem on a 2-D array architecture. <\/jats:p>","DOI":"10.1142\/s0129054103001601","type":"journal-article","created":{"date-parts":[[2003,6,25]],"date-time":"2003-06-25T00:53:09Z","timestamp":1056502389000},"page":"79-98","source":"Crossref","is-referenced-by-count":0,"title":["SCALABLE AND OPTIMAL SPEED-UP PARALLEL ALGORITHMS  FOR TEMPLATE MATCHING ON ARRAYS WITH RECONFIGURABLE OPTICAL BUSES"],"prefix":"10.1142","volume":"14","author":[{"given":"CHIN-HSIUNG","family":"WU","sequence":"first","affiliation":[{"name":"Department of Information Management, Chinese Naval Academy, Kaohsiung, Taiwan, R. 0. C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SHI-JINN","family":"HORNG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan, R. 0. C."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90084-M"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626496000339"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/12.16495"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90130-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.3.246"},{"key":"rf9","first-page":"554","volume":"6","author":"Kao T. W.","journal-title":"IEEE Trans. Parallel and Distributed Systems"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1364\/AO.29.002024"},{"key":"rf11","first-page":"705","volume":"9","author":"Li K.","journal-title":"IEEE Trans. Parallel and Distributed systems"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626495000047"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0262-8856(92)90035-2"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(97)10013-5"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1080\/10637199608915554"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1142\/S012905419800009X"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/12.223677"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675976"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1998.0638"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1109\/71.80177"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1644"},{"key":"rf24","first-page":"1281","volume":"12","author":"Wu C. H.","journal-title":"IEEE Trans. Parallel and Distributed Systems"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1821"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103001601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:26:37Z","timestamp":1565191597000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":20,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,2]]}},"alternative-id":["10.1142\/S0129054103001601"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103001601","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}