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

摘要

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