CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズムCache-conscious parallel PAIDの提案 Cache-Conscious Parallel PAID: A Parallel Sequential Pattern Mining Algorithm with the Effective Use of Cache Memory

この論文にアクセスする

この論文をさがす

抄録

本論文では,既存の時系列パターンマイニングアルゴリズム PAID を対象に,CPU のキャッシュミスの軽減を目的とした改良手法の提案を行う.時系列パターンマイニングでは,データベースの規模やパターンの抽出に用いられる閾値によって非常に多くの処理時間が必要とされることが問題とされており,過去の研究においてアルゴリズムや並列化の提案が行われてきた.また,時系列パターンマイニングではデータベース全体に対して非常に多くの反復的なアクセスが生じる傾向にあり,キャッシュミスが発生しやすいと考えられる.そのため,大規模なデータベースや小さな閾値を利用した場合のキャッシュミスによるレイテンシは,全体の処理時間に対して無視できない可能性がある.PAID アルゴリズムにおいても同様に反復的なアクセスが生じるデータ構造があり,キャッシュミスが起こる可能性がある.このため,処理対象のアクセスパターンとデータ構造等の改良による特定のデータ構造に対するキャッシュミスの軽減手法を提案する.In this paper, we propose a technique to reduce the memory access latency caused by cache misses in PAID algorithm. Since sequential pattern mining algorithms generally require long time depending on the database size and the minimum support value, many methods have been proposed such as efficient algorithms and their parallelization. The sequential pattern mining tends to repeat database scans, which frequently cause cache misses. The frequent cache misses cannot be ignored, when, in particular, a low minimum support value is set. In PAID algorithm, cache misses happen in some data structures which are accessed repeatedly. Therefore, we propose a method to improve the data structures and their access patterns so that cache misses can reduce.

収録刊行物

  • 研究報告データベースシステム(DBS)

    研究報告データベースシステム(DBS) 2010-DBS-151(9), 1-7, 2010-11-05

    情報処理学会

各種コード

  • NII論文ID(NAID)
    110008003690
  • NII書誌ID(NCID)
    AN10112482
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    1884-0930
  • NDL 記事登録ID
    025059343
  • NDL 請求記号
    YH247-911
  • データ提供元
    NDL  NII-ELS  IPSJ 
ページトップへ