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

摘要

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