分離連鎖法におけるバケット方式を用いたときのアクセス回数について

概要

論文の詳細を見る
分散記憶法は2次記憶系を含むランダムアクセスのアドレスシングの問題に対しても有効に適用できる. ファイルへのアクセス方法としては, 複数個の見出しをひとまとめにして取り扱うバケット方式がある. Knuthは, このバケット方式で, 各見出しの探索頻度が一様であるという仮定のもと, 衝突処理のうち分離連鎖法, 合併連鎖法, 線形法について, すでにアクセス回数を評価する表現式を提案しているが, その導出前提に検討を要する問題がある. 本論文では, 分離連鎖法において, 各見出しの探索頻度を考慮する観点から, アクセス回数の評価式を導出し, 探索頻度に具体的な確率分布を与えたときのアクセス回数を評価する. とくに, 各見出しの探索頻度が一様である場合, Knuthの表現式と比較検討し, その相違点を指摘する. そして, その原因が導出前提の設定の違い, すなわち, 確率変数の考え方の違いであることを示す. 次に, 適切なパケットサイズの算定が行えるように, あふれの起こる確率を評価できる表現式を導出し, 具体的にあふれの起こる確率を考察する.
一般社団法人情報処理学会の論文
1984-01-15