論文メモ Designing Access Methods: The RUM Conjecture
April 26, 2021データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。
予想の前提には、主記憶と補助記憶間の容量とIO速度のトレードオフがある。
以下の図は、前提にある記憶装置の階層構造を示す。
RO, MO, WOはread, memory, write overheadを意味する。
上層ほど、各オーバヘッドは小さいが、同時に容量も小さい。
論文におけるオーバーヘッドの意味はamplificationに近い。
読み込みのオーバーヘッドは、読み込まれた主記憶と補助記憶のデータ量を実際に取得したデータ容量で割った値にあたる。
更新のオーバヘッドは物理的に更新されたデータサイズを論理的に更新されたデータサイズで割った値であり、メモリのオーバーヘッドは消費される主記憶と補助記憶の消費データサイズの和を補助記憶のサイズで割った値に該当する。
主要なデータ構造を最適化対象をもとにマッピングすると、次の図の位置関係になる。
論文をこちらからダウンロードできます。 画像は論文から引用されています。