LRU-k法の簡単な近似

スポンサーリンク

概要

• 論文の詳細を見る

• LRU-k法は統計的視点から最適なページ置換えアルゴリズムであることが知られている。この方法は、ページミスが起きたとき最近から遡ってk番目のリクエストの順序情報を利用してページ置換えを行うものである。しかし実際にこの方法をインプリメントするには項目数nに比例するO(n)個の記憶領域が必要なので実現は難しい。我々は履歴情報を用いることのない単純な方法を提案し、ランダムウォークの手法を用いてその性能を評価する。項目の挿入が一様に分布するという仮定のもとで、我々の方法における項目の平均的振る舞いはLRU-k法におけるそれと一致する。さらに発展として、高速メモリサイズmに対しO(m)個の記憶領域が使えると仮定したときに、LRU-2法のさらなる近似が可能であることを示す。

• 社団法人電子情報通信学会の論文
• 2002-12-12

著者

• 玉置 光司

  愛知大学経営学部

• 木庭 淳

  神戸商科大学

• V. Mazalov

  Institute Of Applied Mathematical Research Karelian Research Centre

• 藤井 剛

  神戸商科大学管理科学科

関連論文

• Lookahead Scheduling Requests for Multi-size Page Caching
• 局所発見不可能な故障のゲーム理論的分析
• Sum the multiplicative odds to one and stop (不確実・不確定性下での意思決定過程--RIMS研究集会報告集)
• Optimal choice of the best available applicant in the full-information models with uncertain selection (不確実性と意思決定の数理--RIMS研究集会報告集)
• 2-E-13 Optimal Choice of the Best Available Applicant in the Full-information Models with Uncertain Selection
• 局所発見不可能な故障のゲーム理論的分析
• 1-F-4 ベルヌーイ過程に付随する最適停止問題(動的計画)
• 木型ネットワークにおける単一コータリのニ基準配置問題に関する数値実験
• 木型ネットワークにおける単一コータリーの二基準配置問題に関する数値実験
• Lookahead Scheduling Requests for Efficient Paging (Algorithms and Theory of Computing)
• 動的クラスタリングへ向けて
• 「最適化とその応用」研究部会終了報告(ペーパーフェア)
• 「最適化とその応用」研究部会中間報告(ペーパーフェア)
• LRU-k法の簡単な近似
• Duration Problem and the Ballot Problem
• AN EXPLICIT FORMULA FOR THE LIMITING OPTIMAL VALUE IN THE FULL INFORMATION DURATION PROBLEM
• 連鎖的アボートのない多版先読みスケジューラ
• デ-タベ-スシステムにおける動的な版の選択を行うk版先読みスケジュ-ラ
• 動的な版の選択を行う1版先読みスケジュ-ラ
• Avoiding almost all faulty privileges in almost linear convergence time (Essays in Commemoration of the Fortieth Anniversary of Department of Management Science)
• A Note on Expected Staying Time Related to Paging
• 二次記憶を用いて収束中の安全性を改善する方法について
• A GAME THEORETIC APPROACH TO PROBE COMPLEXITY IN QUORUM SUSTEMS
• アドホックネットワークに対する自己安定的トークン伝達法
• リクエストに基づいた自己安定的トークン伝達法
• トークン伝達中における仮想リングの反復的構築
• LRUスタックの最適な再構築方策について
• An Extended Depth-first Search : How to Decrease Backtracking (New Developments of Theory of Computation and Algorithms)
• 自己安定深さ優先トークン伝達方式における故障特権の回避について
• 故障度適応封じ込め特性をもつ故障特権の回避
• 全体合理性を満たした自己安定的リンク形成アルゴリズム
• 2より小さい近似比率をもつ自己安定的頂点被覆(セッション1)
• Maximizing the probability of stopping on any of the last m successes in Bernoulli trials with random horizon (不確実性下における意思決定問題--RIMS研究集会報告集)
• An Explicit Formula for the Limiting Optimal Gain in the Full Information Duration Problem (不確実性の下での意思決定の数理 研究集会報告集)
• A BAYESIAN SEQUENTIAL SCHEDULING ON TWO PARALLEL MACHINES(MATHEMATICAL OPTIMIZATION AND ITS APPLICATIONS)
• 1-A-1 Sum the Multiplicative Odds to One and Stop
• 1-G-8 A Generalization of the Secretary Problem with Rank-based Selection and Cardinal Payoffs
• A note on the Stewart's secretary problem (最適化問題における確率モデルの展開と応用--RIMS共同研究報告集)
• 出現個数がランダムな場合の odds-theorem(不確実性を含む意思決定の数理とその応用)
• Markov version of Bruss' odds-theorem (情報決定過程論の展開 RIMS共同研究報告集)
• ベルヌーイ過程に付随する最適停止問題(情報決定過程論の展開)
• A Note on the Best-Choice Problem Related to the Weighted Random Permutation (不確実性の下での意思決定と数理モデル--RIMS研究集会報告集)
• The PPP Approach to Robbins' Problem of Minimizing the Expected Rank (Development of the Dynamic Systems under Uncertainty)
• An Optimal Employment Problem with Multiple-Choice and Partial Recall (不確実性と意思決定数理の諸問題 研究集会報告集)
• A multiple choice loss minimization problem with partial recall
• Full-information rank minimization problem in PPP
• 応募者数が一般化された一様分布の下でのGusein-Zade問題(動的計画)
• 応募者数が一般化された一様分布の下でのGusein-Zade問題 (不確実性の下での意思決定の数理)
• Multiple Choice Problems Related to the Duration of the Secretary Problem
• 応募者数が一般化された一様分布に従う秘書問題 (不確実性の下での数理モデルの構築と最適化)
• 2-F-3 Optimal Stopping with Random Horizon with Application to the Duration Problem
• Optimal Stopping Rules for the Random Horizon Duration Problems (Mathematical Decision Making under Uncertainty and Ambiguity, and Related Topics)
• 2-A-2 Recognizing Any of the Last m Successes in Bernoulli Trials with Random Horizon
• 1-B-6 Optimal Stopping Rules for the Random Horizon Duration Problem with Constant Occurrence Probability
• 1-G-7 分散システム故障回復への応用を考慮した効率的機雷探索(ゲーム理論(1))
• Optimal Stopping Rule for the Full-Information Duration Problem With Random Horizon (Stochastic Decision Analysis)

もっと見る 閉じる

スポンサーリンク