計算クラスタ上で文字列の類似度を計算するための並列アルゴリズム(経営情報科学部:情報科学科コンピュータシステム専攻)

概要

論文の詳細を見る
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.
愛知工業大学の論文
2005-03-31