キャッシュを使った頻出アイテムの抽出

吉田 健一  勝野 聡  藤田 昌克  鶴 正人  阿野 茂浩  山崎 克之  

誌名
電子情報通信学会論文誌 B   Vol.J88-B   No.10   pp.2012-2021
発行日: 2005/10/01
Online ISSN: 
Print ISSN: 1344-4697
論文種別: 特集論文 (インターネットアーキテクチャ技術論文特集)
専門分野: トラヒック解析
キーワード: 
キャッシュ,  LRU,  頻出アイテム,  

本文: PDF(4.3MB)
>>論文を購入


あらまし: 
バスケット解析の基本手順の一部である頻出アイテムの抽出をオンラインで高速に行うための手法としてメモリキャッシュを使う方法を提案する.また,この手法の動作特性を解析し,頻出アイテム抽出のためのキャッシュ管理にはLRUよりもランダムベースのもので性能のよいものがあることと,データがZipfの法則に基づく場合ランダムベースのアルゴリズムが通常のヒット率においてもLRUより優れていることを示す.これは,ここ数十年標準的なキャッシュ管理の方法として用いられてきたLRUまたはLRUベースの手法に対して,randomベースの手法が有望なことを示唆している点で注意を要する.