論文メモ Designing Access Methods: The RUM Conjecture

April 26, 2021

データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。

予想の前提には、主記憶と補助記憶間の容量とIO速度のトレードオフがある。 以下の図は、前提にある記憶装置の階層構造を示す。 上層ほど、各オーバヘッドは小さいが、同時に容量も小さい。 hierarchies 論文におけるオーバーヘッドはamplificationの意味に近い。 読み込みのオーバーヘッドは、読み込まれた主記憶と補助記憶のデータ量を実際に取得したデータ容量で割った値にあたる。 更新のオーバヘッドは物理的に更新されたデータサイズを論理的に更新されたデータサイズで割った値であり、メモリのオーバーヘッドは消費される主記憶と補助記憶の消費データサイズの和を補助記憶のサイズで割った値に該当する。 主要なデータ構造を最適化対象をもとにマッピングすると、次の図の位置関係になる。 data_structures

論文をこちらからダウンロードできます。 画像は論文から引用されています。