計算クラスタ上で文字列の類似度を計算するための並列アルゴリズム

Abstract

We present a parallel algorithm to calculate the similarity of two strings on computers connected by a local area network, called a cluster of computers. Let the length of each string be n and the number of the computers p. We show that the parallel algorithm can solve the problem in time [numerical formula] when [numerical formula], and, therefore, that the algorithm can do it in time [numerical formula] especially when [numerical formula], where B is (physical time for the computer to transmit one word through the network)/(physical time for the computer to execute one instruction on CPU) (≃100). Since the time complexity of the sequential algorithm is O(n^2), the parallel algorithm is faster than the sequential algorithm.