WEKO3
-
RootNode
アイテム
CC-PAID：CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/74656
https://ipsj.ixsq.nii.ac.jp/records/7465622bb368e-7f1f-428b-ba66-ad1cb287e965
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOD0402009.pdf (2.6 MB)
|
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-07-01 | |||||||
| タイトル | ||||||||
| タイトル | CC-PAID：CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | CC-PAID: A Cache-conscious Parallel Sequential Pattern Mining Algorithm | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 研究論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 奈良先端科学技術大学院大学情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 奈良先端科学技術大学院大学情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 筑波大学大学院図書館情報メディア研究科 | ||||||||
| 著者所属 | ||||||||
| 山形大学工学部システム創成工学科 | ||||||||
| 著者所属 | ||||||||
| 奈良先端科学技術大学院大学情報科学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Science，Nara Institute of Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Science，Nara Institute of Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Library, Information and Media Studies, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Systems Innovation Engineering, Yamagata University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Science，Nara Institute of Science and Technology | ||||||||
| 著者名 |
松原, 裕貴
宮崎, 純
藤澤, 誠
天野, 敏之
加藤, 博一
× 松原, 裕貴 宮崎, 純 藤澤, 誠 天野, 敏之 加藤, 博一
|
|||||||
| 著者名(英) |
Yuki, Matsubara
Jun, Miyazaki
Makoto, Fujisawa
Toshiyuki, Amano
Hirokazu, Kato
× Yuki, Matsubara Jun, Miyazaki Makoto, Fujisawa Toshiyuki, Amano Hirokazu, Kato
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では，既存の時系列パターンマイニングアルゴリズムPAIDを対象に，CPUのキャッシュミスの軽減による処理時間の短縮を目的とした改良手法の提案を行う．時系列パターンマイニングでは，データベースの規模やパターンの抽出に用いられる閾値によって非常に長い処理時間が必要とされることが問題とされており，過去の研究においてアルゴリズムや並列化の提案が行われてきた．また，処理対象となるデータベース全体に対して多くの反復的なアクセスが生じ，キャッシュミスが発生しやすいため，大規模なデータベースや小さな閾値を利用した場合，そのレイテンシは全体の処理時間に対して無視できない可能性がある．PAIDアルゴリズムにおいても同様に反復的なアクセスが生じるデータ構造があり，キャッシュミスが起こる可能性が考えられる．そのため，提案手法では処理対象へのアクセスパターンの改良により，PAIDアルゴリズムの特定のデータ構造での時間的局所性を向上させ，キャッシュミスの軽減を行う．また，処理時間を短縮するために並列化も行い，性能評価によりこれらの有効性の確認を行う． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464847 | |||||||
| 書誌情報 |
情報処理学会論文誌データベース（TOD） 巻 4, 号 2, p. 88-100, 発行日 2011-07-01 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7799 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
