{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T14:53:15Z","timestamp":1648565595775},"reference-count":24,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2014]]},"DOI":"10.1587\/transinf.2014pap0011","type":"journal-article","created":{"date-parts":[[2014,11,30]],"date-time":"2014-11-30T23:30:16Z","timestamp":1417390216000},"page":"3063-3071","source":"Crossref","is-referenced-by-count":3,"title":["An Optimal Implementation of the Approximate String Matching on the Hierarchical Memory Machine, with Performance Evaluation on the GPU"],"prefix":"10.1587","volume":"E97.D","author":[{"given":"Duhu","family":"MAN","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Hiroshima University"}]},{"given":"Koji","family":"NAKANO","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Hiroshima University"}]},{"given":"Yasuaki","family":"ITO","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Hiroshima University"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] W.W. Hwu, GPU Computing Gems Emerald Edition, Morgan Kaufmann, 2011."},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] K. Ogawa, Y. Ito, and K. Nakano, \u201cEfficient Canny edge detection using a GPU,\u201d Proc. International Conference on Networking and Computing, pp.279-280, Nov. 2010.","DOI":"10.1109\/IC-NC.2010.13"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] D. Man, K. Uda, Y. Ito, and K. Nakano, \u201cA GPU implementation of computing Euclidean distance map with efficient memory access,\u201d Proc. International Conference on Networking and Computing, pp.68-76, Dec. 2011.","DOI":"10.1109\/ICNC.2011.19"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] A. Uchida, Y. Ito, and K. Nakano, \u201cFast and accurate template matching using pixel rearrangement on the GPU,\u201d Proc. International Conference on Networking and Computing, pp.153-159, Dec. 2011.","DOI":"10.1109\/ICNC.2011.30"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] Y. Ito, K. Ogawa, and K. Nakano, \u201cFast ellipse detection algorithm using Hough transform on the GPU,\u201d Proc. International Conference on Networking and Computing, pp.313-319, Dec. 2011.","DOI":"10.1109\/ICNC.2011.61"},{"key":"6","unstructured":"[6] NVIDIA Corporation, \u201cNVIDIA CUDA C programming guide version 5.0,\u201d 2012."},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] D. Man, K. Uda, H. Ueyama, Y. Ito, and K. Nakano, \u201cImplementations of a parallel algorithm for computing euclidean distance map in multicore processors and GPUs,\u201d Int. J. Networking and Computing, vol.1, no.2, pp.260-276, July 2011.","DOI":"10.15803\/ijnc.1.2_260"},{"key":"8","unstructured":"[8] NVIDIA Corporation, \u201cNVIDIA CUDA C best practice guide version 3.1,\u201d 2010."},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] K. Nishida, Y. Ito, and K. Nakano, \u201cAccelerating the dynamic programming for the optial poygon triangulation on the GPU,\u201d Proc. International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP, LNCS 7439), pp.1-15, Sept. 2012.","DOI":"10.1007\/978-3-642-33078-0_1"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] K. Nakano, \u201cSimple memory machine models for GPUs,\u201d Proc. International Parallel and Distributed Processing Symposium Workshops, pp.788-797, May 2012.","DOI":"10.1109\/IPDPSW.2012.98"},{"key":"11","unstructured":"[11] A.V. Aho, J.D. Ullman, and J.E. Hopcroft, Data Structures and Algorithms, Addison Wesley, 1983."},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] M.J. Flynn, \u201cSome computer organizations and their effectiveness,\u201d IEEE Trans. Comput., vol.C-21, pp.948-960, 1972.","DOI":"10.1109\/TC.1972.5009071"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] K. Nakano, \u201cThe hierarchical memory machine model for GPUs,\u201d Proc. International Parallel and Distributed Processing Symposium Workshops, pp.591-600, May 2013.","DOI":"10.1109\/IPDPSW.2013.17"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] P.H. Sellers, \u201cThe theory and computation of evolutionary distances: Pattern recognition,\u201d J. Algorithms, vol.1, no.4, pp.359-373, Dec. 1980.","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] E. Ukkonen, \u201cAlgorithms for approximate string matching,\u201d Information and Control, vol.64, no.1-3, pp.100-118, Jan.-March 1985.","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] G. Myers, \u201cA fast bit-vector algorithm for approximate string matching based on dynamic programming,\u201d J. ACM, vol.46, no.3, pp.395-415, May 1999.","DOI":"10.1145\/316542.316550"},{"key":"17","unstructured":"[17] Y. Utan, M. Inagi, S. Wakabayashi, and S. Nagayama, \u201cA GPGPU implementation of approximate string matching with regular expression operators and comparison with its FPGA implementation,\u201d Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications, July 2012."},{"key":"18","unstructured":"[18] Y. Liu, L. Guo, J. Li, M. Ren, and K. Li, \u201cParallel algorithms for approximate string matching with k mismatches on cuda,\u201d Proc. International Parallel and Distributed Processing Symposium Workshops, pp.2414-2422, May 2012."},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] K. Nakano, \u201cEfficient implementations of the approximate string matching on the memory machine models,\u201d Proc. International Conference on Networking and Computing, pp.233-239, Dec. 2012.","DOI":"10.1109\/ICNC.2012.43"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] A. Kasagi, K. Nakano, and Y. Ito, \u201cAn implementation of conflict-free off-line permutation on the GPU,\u201d Proc. International Conference on Networking and Computing, pp.226-232, 2012.","DOI":"10.1109\/ICNC.2012.42"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] K. Nakano, S. Matsumae, and Y. Ito, \u201cThe random address shift to reduce the memory access congestion on the discrete memory machine,\u201d Proc. International Symposium on Computing and Networking, pp.95-103, Dec. 2013.","DOI":"10.1109\/CANDAR.2013.21"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] K. Nakano, \u201cSequential memory access on the unified memory machine with application to the dynamic programming,\u201d Proc. International Symposium on Computing and Networking, pp.85-94, Dec. 2013.","DOI":"10.1109\/CANDAR.2013.20"},{"key":"23","unstructured":"[23] T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, 1990."},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] K. Nakano, \u201cAn optimal parallel prefix-sums algorithm on the memory machine models for GPUs,\u201d Proc. International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP, LNCS 7439), pp.99-113, Sept. 2012.","DOI":"10.1007\/978-3-642-33078-0_8"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E97.D\/12\/E97.D_2014PAP0011\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T06:12:23Z","timestamp":1619417543000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E97.D\/12\/E97.D_2014PAP0011\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":24,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2014pap0011","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}