Optimal implementations of the approximate string matching and the approximate discrete signal matching on the memory machine models

REFERENCES

• A.V.Aho, J.D.Ullman, and J.E.Hopcroft, Data Structures and Algorithms, Addison Wesley, Amsterdam, 1983.
   Google Scholar
• R.H.Bisseling, Parallel Scientific Computation: A Structured Approach using BSP and MPI, Oxford University Press, Oxford, UK, 2004.
   Google Scholar
• T.H.Cormen, C.E.Leiserson, and R.L.Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.
   Google Scholar
• D.Culler, R.Karp, D.Patterson, A.Sahay, K.E.Schauser, E.Santos, R.Subramonian, and T.Eickenvon, LogP: towards a realistic model of parallel computation, in Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM1993, pp. 1–12.
   Google Scholar
• M.J.Flynn, Some computer organizations and their effectiveness, IEEE Trans. Comput.C-21 (1972), pp. 948–960.
   Web of Science ®Google Scholar
• A.Gibbons and W.Rytter, Efficient Parallel Algorithms, Cambridge University Press, Cambridge, UK, 1988.
   Google Scholar
• A.Grama, G.Karypis, V.Kumar, and A.Gupta, Introduction to Parallel Computing, Addison Wesley, Amsterdam, 2003.
   Google Scholar
• W.W.Hwu, GPU Computing Gems, Emerald Edition, Morgan Kaufmann, Burlington, MA, 2011.
   Google Scholar
• F.T.Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Francisco, CA, 1991.
   Google Scholar
• Y.Liu, L.Guo, J.Li, M.Ren, and K.Li, Parallel algorithms for approximate string matching with k mismatches on CUDA, in Proceedings of the International Parallel and Distributed Processing Symposium Workshops, May, IEEE CS Press, 2012, pp. 2414–2422.
   Google Scholar
• D.Man, K.Uda, H.Ueyama, Y.Ito, and K.Nakano, Implementations of a parallel algorithm for computing Euclidean distance map in multicore processors and GPUs, Int. J. Networking Comput.1 (2011), pp. 260–276.
   Google Scholar
• D.Man, K.Uda, Y.Ito, and K.Nakano, A GPU implementation of computing euclidean distance map with efficient memory access, in Proceedings of the International Conference on Networking and Computing, December, IEEE CS Press, 2011, pp. 68–76.
   Google Scholar
• M.Müller, Chapter 4: Dynamic time warping, in Information Retrieval for Music and Motion, Springer, Heidelberg Germany, 2007, pp. 69–84.
   Google Scholar
• G.Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, J. ACM46 (1999), pp. 395–415.
   Web of Science ®Google Scholar
• K.Nakano, An optimal parallel prefix-sums algorithm on the memory machine models for GPUs, in Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP, LNCS 7439), Septemper, Springer, 2012, pp. 99–113.
   Google Scholar
• K.Nakano, Simple memory machine models for GPUs, in Proceedings of the International Parallel and Distributed Processing Symposium Workshops, May, IEEE CS Press, 2012, pp. 788–797.
   Google Scholar
• K.Nishida, Y.Ito, and K.Nakano, Accelerating the dynamic programming for the optial poygon triangulation on the GPU, in Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP, LNCS 7439), September, IEEE CS Press, 2012, pp. 1–15.
   Google Scholar
• NVIDIA Corporation, NVIDIA CUDA C Best Practice Guide Version 3.1, Santa Clara, CA, 2010.
   Google Scholar
• NVIDIA Corporation, NVIDIA CUDA C Programming Guide Version 4.0, Santa Clara, CA, 2011.
   Google Scholar
• M.J.Quinn, Parallel Computing: Theory and Practice, McGraw-Hill, New York, 1994.
   Google Scholar
• H.Sakoe and S.Chiba, Dynamic programming algorithm optimization for spoken word recognition, IEEE Trans, Acoust. Speech Signal Process26 (1978), pp. 43–49.
   Google Scholar
• P.H.Sellers, The theory and computation of evolutionary distances: Pattern recognition, J. Algorithms1 (1980), pp. 359–373.
   Google Scholar
• A.Uchida, Y.Ito, and K.Nakano, Fast and accurate template matching using pixel rearrangement on the GPU, in Proceedings of the International Conference on Networking and Computing, December, IEEE CS Press, 2011, pp. 153–159.
   Google Scholar
• E.Ukkonen, Algorithms for approximate string matching, Inform. Control64 (1985), pp. 100–118.
   Google Scholar
• R.Vaidyanathan and J.L.Trahan, Dynamic Reconfiguration: Architectures and Algorithms, Kluwer Academic/Plenum Publishers, New York, 2004.
   Google Scholar
• L.G.Valiant, A bridging model for multi-core computing, J. Comput. Syst. Sci.77 (2011), pp. 154–166.
   Web of Science ®Google Scholar