線形法におけるパケット方式を用いたときのアクセス回数について

概要

論文の詳細を見る
分散記憶法を2次記憶系での探索に利用するとき, ファイルへのアクセス方法としては, 複数個の見出しをひとまとめにして取り扱うパケット方式がある. この方式で, あふれの処理に線形法を用いたとき, アクセス回数に関してKnuthが提案した評価式は, 見出しの探索頻度が一様であるとの仮定の下で, アクセス回数の近似値を評価するものである. 本論文では, 各見出しの探索頻度を考慮する立場から, アクセス回数を評価する表現式を導き出し, 探索頻度に具体的な確率分布を与えたときのアクセス回数を評価する. とくに, 探索頻度を一様と仮定したとき, 従来の評価式では, なぜアクセス回数の厳密な評価でなく近似値を評価するのか, その導出過程を示し検討する. また, あふれの処理として, 分離連鎖法と線形法を用いたときのアクセス回数を評価した結果, パケットサイズが大きくかつ表占有率が大きい場合には, 線形法が分離連鎖法よりも探索効率がよいことを示す.
一般社団法人情報処理学会の論文
1985-01-15