文献

J-GLOBAL ID：201502220092190110   整理番号：15A1150415

接頭部和計算に基づく近似文字列探索の並列化

Parallelization of Approximate String Matching Based on Computation of Prefix Sums

著者 (3件)： 三谷康晃 (大阪大 大学院情報科学研究科) ,  伊野文彦 (大阪大 大学院情報科学研究科) ,  萩原兼一 (大阪大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 174(CPSY2015 16-44)  ページ： 229-234  発行年： 2015年07月28日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文は,文字列探索の高速化を目的として,探索法の1つであるShift-Or法の並列化手法を提案する。提案手法はShift-Or法を接頭部和計算に帰着することで並列化する。接頭部和計算はワープ内のスレッドが連続領域を参照するように並列処理できるため,GPU(Graphics Processing Unit)上で効率よくShift-Or法を実現できる。本論文では,まず,2種類の2項演算を定義し,これらを用いてShift-Or法の処理を接頭部和計算に帰着するための手順を示す。さらに,接頭部和計算を並列処理するために必要となる各演算の結合性を証明する。評価実験では,セグメント分割に基づく既存手法と提案手法をGPU上で比較した。その結果,完全一致文字列探索に対して,提案手法は既存手法と比較して約1.5倍の高速化を達成した。一方,近似文字列探索に対しては,約76~104%の性能に留まった。(著者抄録)

シソーラス用語： *マッチング ,  並列処理 ,  *専用プロセッサ ,  高速化 ,  演算方式 ,  方式 ,  並列化 ,  スレッド ,  連結性 ,  実験 ,  分割 ,  *GPU【プロセッサ】 ,  探索法 ,  評価実験
準シソーラス用語： shift-or法 ,  セグメント分割 ,  接頭部和計算 ,  *文字列検索

分類 (2件)： 検索技術  (AC06020S) ,  専用演算制御装置  (JC04030Y)

引用文献 (11件)：

• V.I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,“ Doklady Akademii Nauk SSSR, vol.163, no.4, pp.845-848, Aug. 1965.
• G. Vasiliadis, S. Antonatos, M. Polychronakis, E.P. Markatos, and S. Ioannidis, “Gnort: High performance network intrusion detection using graphics processors,“ Proc. 11th Int'l Symp. Recent Advances in Intrusion Detection (RAID'08), pp.116-134, Sept. 2008.
• A. Tumeo, O. Villa, and D. Sciuto, “Efficient pattern matching on GPUs for intrusion detection systems,“ Proc. 7th Int'l Conf. Computing Frontiers (CF'10), pp.87-88, May 2010.
• A. Tumeo and O. Villa, “Accelerating DNA analysis applications on GPU clusters,“ Proc. 8th Symp. Application Specific Processors (SASP'10), pp.71-76, June 2010.
• S. Gog, K. Karhu, and J. Kkkkainen, “Multi-pattern matching with bidirectional indexes,“ Proc. 18th Intl Computing and Combinatorics Conf. (COCOON'12), pp.384-395, Aug. 2012.

タイトルに関連する用語 (5件)： 計算 ,  近似 ,  文字列 ,  探索 ,  並列化