論文メモ Designing Access Methods: The RUM Conjecture
データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。
Posts
論文メモ A comparison of Fractal Trees to Log-Structured Merge (LSM) Trees
Fractal Treeは、B+木のルートと節にバッファをもたせるデータ構造にあたる。 そのFractal TreeのamplificationをB+木やLSM Treeのそれと比較した。 議論になるamplificationは、write, read, spaceの3つで、write amplificationはアプリケーションが書き込むデータ量に対して実際にストレージに書き込まれたデータ量を表す。 read amplificationはクエリの実行に必要なI/Oの回数、space amplificationは仕組み上避けられない断片化や一時的なデータのコピーに該当する。
論文メモ Fast Intersection Algorithms for Sorted Sequences
ソートされたシーケンスの直積を高速に求めるアルゴリズム Double Binary Searchを示した。 2つのシーケンス\(D\), \(Q\)があり、\(\mid D\mid=n\), \(\mid Q\mid=m\), \(n >= m\)であれば、平均と最悪時間計算量が、それぞれ、\(\mathcal{O}(m\log(n/m))\), \(m\)になる。 本アルゴリズムは、Web検索エンジンで大きなシーケンスの直積を高速に求めるために開発された。
論文メモ The Log-Structured Merge-Tree (LSM-Tree)
LSM-Treeは、検索より挿入や削除が多い用途に向いたインデックス構造であり、例えば履歴テーブルやログの保存につかえる。 メモリにある1つ木とディスク上の1つ以上の木からなり、直近の挿入や削除をメモリの木で管理する。 メモリの木の大きさがしきい値を超えたとき、メモリの木の葉をディスクの木に移す。 移動時は、ディスク上の木の葉とメモリの葉をマージソートの要領でソートし、ソートした葉をディスクの新しい連続領域に書き込む。 連続領域に書き込み、アームの移動やディスクの回転を減らすことで、高速に挿入や削除ができる。 一方、検索速度は、複数の木を探索しなければならないために、1つの木でインデックスを構成するB木に劣る。
論文メモ The Design and Implementation of a Log-Structured File System
Log-structured file system(LFS)は、91年に提唱されたHDD向けのファイルシステムであり、バッファリングした変更をディスクの連続領域に一度に書き込むことで、小さなファイルを大量に高速で書き込める。 また、クラッシュからのリカバリも、ディスク全体ではなくチェックポイント以降に追記された箇所だけを検査すればよいので、高速になる。
論文メモ ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging
ARIES/IMは、B+木への直列化可能性のある並行処理とログ先行書き込み(Write-Ahead Logging, WAL)による復元を実現する。 ARIES/IMのベースには、先行研究のARIESがある。 復元手順はARIESとほとんど変わらない。 キーの参照先にあるデータのレコードとキーを同じロックで保護したり、ロックの代わりにラッチを使ったりすることで、ロックの頻度を下げ、B+木の高速化を実現する。
論文メモ The Ubiquitous B-Tree
B木とその派生データ構造のサーベイ論文で、とくにB+木に重点がおかれている。 B+木は、全てのキーを葉におき、葉を隣接リストでつなぐことで、B木が不得手なシーケンシャルなアクセスを改善する。 これにより、定数オーダーの時間と空間計算量で逐次的にキーにアクセスにできる。 ランダムな検索、挿入、削除にかかる時間、空間計算量はB木と変わらない。 以降はB木のデータ構造を前提としてB+木の概要を説明する。B木について知りたい場合は、B木のオリジナル論文の解説記事を見てほしい。
論文メモ Robust Random Cut Forest Based Anomaly Detection On Streams
Robust Random Cut Forest(RRCT)はストリームデータ向きの異常検知の手法で、Amazon SageMakerから提供されている。 バッチデータと違い、ストリームデータは新たなデータが随時追加、修正される。 RRCTは、特徴の値でデータを2分するノードからなる木の集合であり、データを追加したときに木の集合であるモデルを大きく複雑するものを異常と判定する。
論文メモ Organization and Maintenance of Large Ordered indexes
1972年に発表されたB木のオリジナルの論文。 \(I\)をインデックスの大きさ、\(k\)をハードウェア依存の値とすると、検索、挿入、削除の時間計算量は\(\log_kI\)になる。 ここでのインデックスは、固定長の\((x, \alpha)\)を要素とする連想配列で、最大\(2k\)個のキーを格納できる連続したページ上にある。 \(\alpha\)には、データを保存した1つ以上のレコードへのポインタが格納される。
Space/Time Trade-offs in Hash Coding with Allowable Errors
要素がハッシュ空間にあるかを高速に調べる手法で、ブルームフィルタの名で知られる。 偽陽性を許容し、ハッシュ値の保持に必要な空間を小さすることで、管理できるデータ件数を増やす。 例えば、データベースのストレージで使われており、検索するキーがデータベースに存在するか事前に確かめ、存在しないキーのための不要なディスクの読み取りを省いている。 偽陰性の誤りはない。