木パターンマッチングのための並列アルゴリズム

IR HANDLE Web Site 27 References Open Access

Bibliographic Information

Other Title
  • キ パターン マッチング ノ タメ ノ ヘイレツ アルゴリズム
  • A Parallel Algorithm for Tree Pattern Matching

Search this article

Abstract

テキスト木tとパターン木pが与えられたとき，tの部分木でpと照合するものを見つける処理を木パターンマッチングと言う．本論文では木パターンマッチングを行う並列アルゴリズムを提案する．tとpのサイズをそれぞれn，mとするとき，提案するアルゴリズムはCREW-PRAM上で（mn/logn）台のプロセッサを使用しO（logn）時間で木パターンマッチングを行う．これまでに知られているCREW-PRAM上でのアルゴリズムは，（mn/log2n）台のプロセッサを使用し，計算時間がO（log2n）であったので，本論文の結果は計算時間を改善する．また，プロセッサの割当て方を具体的に与えている．

Journal

References(27)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top