@article{oai:ipsj.ixsq.nii.ac.jp:00074656,
 author = {松原, 裕貴 and 宮崎, 純 and 藤澤, 誠 and 天野, 敏之 and 加藤, 博一 and Yuki, Matsubara and Jun, Miyazaki and Makoto, Fujisawa and Toshiyuki, Amano and Hirokazu, Kato},
 issue = {2},
 journal = {情報処理学会論文誌データベース（TOD）},
 month = {Jul},
 note = {本論文では，既存の時系列パターンマイニングアルゴリズムPAIDを対象に，CPUのキャッシュミスの軽減による処理時間の短縮を目的とした改良手法の提案を行う．時系列パターンマイニングでは，データベースの規模やパターンの抽出に用いられる閾値によって非常に長い処理時間が必要とされることが問題とされており，過去の研究においてアルゴリズムや並列化の提案が行われてきた．また，処理対象となるデータベース全体に対して多くの反復的なアクセスが生じ，キャッシュミスが発生しやすいため，大規模なデータベースや小さな閾値を利用した場合，そのレイテンシは全体の処理時間に対して無視できない可能性がある．PAIDアルゴリズムにおいても同様に反復的なアクセスが生じるデータ構造があり，キャッシュミスが起こる可能性が考えられる．そのため，提案手法では処理対象へのアクセスパターンの改良により，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 new 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 temporal locality of reference increases, which leads to more cache hits. In addition, we also parallelize our method to reduce further execution time. We evaluate the efficiency of our method through some experiments.},
 pages = {88--100},
 title = {CC-PAID：CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズム},
 volume = {4},
 year = {2011}
}