CC-PAID:CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズム

松原裕貴; 宮崎純; 藤澤誠; 天野敏之; 加藤博一

文献

J-GLOBAL ID：201102239938774849 整理番号：11A1900721

CC-PAID:CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズム

CC-PAID: A Cache-conscious Parallel Sequential Pattern Mining Algorithm

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=11A1900721&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=11A1900721&from=J-GLOBAL&jstjournalNo=L7379A") }}

著者 (5件)： , , , ,
資料名：
巻： 2011 号： 1 ページ： ROMBUNNO.DETABESU,VOL.4,NO.2,88-100 発行年： 2011年10月15日
JST資料番号： L7379A ISSN： 1882-7772 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：日本語 (JA)

本論文では,既存の時系列パターンマイニングアルゴリズムPAIDを対象に,CPUのキャッシュミスの軽減による処理時間の短縮を目的とした改良手法の提案を行う。時系列パターンマイニングでは,データベースの規模やパターンの抽出に用いられる閾値によって非常に長い処理時間が必要とされることが問題とされており,過去の研究においてアルゴリズムや並列化の提案が行われてきた。また,処理対象となるデータベース全体に対して多くの反復的なアクセスが生じ,キャッシュミスが発生しやすいため,大規模なデータベースや小さな閾値を利用した場合,そのレイテンシは全体の処理時間に対して無視できない可能性がある。PAIDアルゴリズムにおいても同様に反復的なアクセスが生じるデータ構造があり,キャッシュミスが起こる可能性が考えられる。そのため,提案手法では処理対象へのアクセスパターンの改良により,PAIDアルゴリズムの特定のデータ構造での時間的局所性を向上させ,キャッシュミスの軽減を行う。また,処理時間を短縮するために並列化も行い,性能評価によりこれらの有効性の確認を行う。(著者抄録)

, , , , , , , , ,
,

人工知能 , 記憶方式 , ディジタル計算機方式一般

引用文献 (12件)：

1) Srikant, R. and Agrawal, R.: Mining Sequential Patterns: Generalizations and Per-formance Improvements, Proc. 5th International Conference on Extending Database Technology: Advances in Database Technology, EDBT '96, pp.3-17, London, UK, Springer-Verlag (1996).
2) Zaki, M.J.: Efficient enumeration of frequent sequences, Proc. 7th International Conference on Information and Knowledge Management, CIKM '98, pp.68-75, New York, NY, USA, ACM (1998).
3) Ayres, J., Gehrke, J., Yiu, T. and Flannick, J.: Sequential PAttern mining us-ing a bitmap representation, Proc. 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, pp.429-435, New York, NY, USA, ACM (2002).
4) Pei, J., Han, J., Mortazavi-Asl, B., Wang, J., Pinto, H., Chen, Q., Dayal, U. and Hsu, M.-C.: Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach, IEEE Trans. Knowledge and Data Engineering, Vol.16, pp.1424-1440 (2004).
5) Wang, J., Asanuma, Y., Kodama, E., Takata, T. and Li, J.: Mining Sequential Patterns More Efficiently by Reducing the Cost of Scanning Sequence Databases,情報処理学会論文誌,Vol.47, No.12, pp.3365-3379(2006-12-15).

, , , , , ,

前のページに戻る