講演抄録/キーワード |
講演名 |
2005-01-24 14:30
キャッシュを使った頻出アイテムの抽出 ○吉田健一(筑波大)・鶴 正人(九工大)・勝野 聡(KDDI研) |
抄録 |
(和) |
バスケット解析の基本手順の1部である頻出アイテムの抽出をオンラインで高速に行うための手法としてメモリキャッシュを使う方法を提案する。また、この手法の動作特性を解析し、頻出アイテム抽出の為のキャッシュ管理にはLRUよりもランダムベースのもので性能の良いものがある事と、データがZipf の法則に基づく場合ランダムベースのアルゴリズムが通常のヒット率においてもLRUより優れている事を示す。これは、ここ数十年標準的なキャッシュ管理の方法として用いられてきたLRUまたはLRUベースの手法に対して、randomベースの手法が有望な事を示唆している点で注意を要する。 |
(英) |
In this paper, we propose a cache-based frequent item finding approach. By analyzing the characteristics of the proposed approach, we found: 1) The proposed random-based approach for cache replacement, called random2, outperforms LRU for frequent item finding. 2) The cache hit rate of random2 outperforms that of LRU on the data which follows Zipf's law. Since the recent studies found the generality of the data which follows Zipf's law, and the performance difference of LRU and pure random replacement is not significant, our results also imply the advantage of random cache replacement strategy. |
キーワード |
(和) |
キャッシュ / LRU / 頻出アイテム / / / / / |
(英) |
Cache / LRU / itemset / mining / / / / |
文献情報 |
信学技報, vol. 104, no. 587, KBSE2004-30, pp. 37-41, 2005年1月. |
資料番号 |
KBSE2004-30 |
発行日 |
2005-01-17 (KBSE) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|