HyperDexはキー以外の要素で値を検索できるキーバリューストアで、このキー以外の要素による検索速度がCassandraやMongoDBと比べて12-13倍速い。 キーバリューストアは、RDBMSと比べると、処理速度は速いが、検索条件の機能に乏しい。 HyperDexは、要素数と同数の次元からなるユークリッド空間を構成し、要素のハッシュ値で決まる座標に値をおくことで、キー以外でも高速に検索することを可能にする。 もとのドメインの順序関係を保持するハッシュ関数を使うため、範囲検索もあつかえる。
商用DBMS TransBaseのインデックスをB木からUB木に変え、複数の範囲クエリからなる多次元アクセスを高速化した。 高速な多次元アクセスの拡張を商用DBMSのインデックスに導入することは複雑かつ高コストのように思える。 UB木は、B木をベースにしたインデックスであり、B木のキーの生成とページ分割方法を工夫し、範囲クエリを高速化する。 範囲クエリに向きB木に似たインデックスを使うことで、既存のDBMSの範囲クエリを人々の想定よりも簡単に高速化できることを例示した。 また、既存のインデックスのインターフェースを呼び出す変更ではなく、もとのインデックス自体を変更する当手法には、クエリのオプティマイザを継続して利用できる利点もある。
データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。
Fractal TreeのamplificationをB+木やLSM Treeと比べて整理した。 Fractal Treeは、B+木のルートと節にバッファをもたせるデータ構造にあたる。 議論になるamplificationはwrite, read, spaceの3つで、write amplificationはアプリケーションの書き込むデータ量に対する実際にストレージに書き込まれたデータ量をさす。 read amplificationはクエリの実行に必要なI/Oの回数、space amplificationは仕組み上避けられない断片化や一時的なデータのコピーをさす。
ソートされたシーケンスの直積を高速に求めるアルゴリズム Double Binary Searchを示した。 2つのシーケンス\(D\), \(Q\)があり、\(\mid D\mid=n\), \(\mid Q\mid=m\), \(n >= m\)であれば、平均と最悪時間計算量が、それぞれ、\(\mathcal{O}(m\log(n/m))\), \(m\)になる。 本アルゴリズムは、Web検索エンジンで大きなシーケンスの直積を高速に求めるために開発された。
LSM-Treeは、検索よりも挿入や削除が多い用途むけのインデックス構造であり、例えば履歴テーブルやログの保存につかえる。 メモリにある1つ木とディスク上の1つ以上の木からなり、直近の挿入や削除をメモリの木で管理する。 メモリの木の大きさがしきい値を超えたとき、メモリの木の葉をディスクの木に移す。 移動時は、ディスク上の木の葉とメモリの葉をマージソートの要領でソートし、ソートした葉をディスクの新しい連続領域に書き込む。 連続領域に書き込み、アームの移動やディスクの回転を減らすことで、高速に挿入や削除ができる。 一方、検索速度は、複数の木を探索しなければならず、1本の木でインデックスを構成するB木に劣る。
91年に提唱されたLog-structured file system(LFS)は、バッファリングした変更を、ディスクの連続領域に一度に書き込むことで、小さなファイルの大量の書き込みを高速に処理できる。 また、クラッシュ時のリカバリも、チェックポイント以降に追記された箇所だけを検査すればよく、ディスク全体を参照する必要がないので、高速になる。
ARIES/IMは、B+木への直列化可能性のある並行処理とログ先行書き込み(Write-Ahead Logging, WAL)による復元を実現する。 ARIES/IMのベースには、先行研究のARIESがある。 復元手順は、平行処理の違いによる差異はあるものの、ARIESと大きく変わらない。 キーの参照先にあるデータのレコードとキーを同じロックで保護したり、ロックの代わりにラッチを使ったりすることで、ロックの頻度を下げ、B+木の高速化を実現する。
ファイルインデックスのためのデータ構造B木とB木を改良したデータ構造のサーベイであり、とくにB+木に重点がおかれている。 B+木は、全てのキーを葉に置き、キーを隣接リストに入れて、B木が不得手なシーケンシャルなアクセスを改善する。 これにより、定数オーダーの時間と空間の計算量で次の要素へのアクセスにできる。 ランダムな検索、挿入、削除にかかる時間、空間計算量はB木と変わらない。 以降はB木のデータ構造を前提としてB+木の概要を説明する。B木について知りたい場合は、B木のオリジナル論文の解説記事を参照してほしい。
ストリームデータ向けの異常検知の手法、Robust Random Cut Forestを提唱した。 ストリームデータをあつかうには、バッチデータと違い、データが随時追加、修正されることに対応できなければならない。 Robust Random Cut Forestは、特徴の値でデータを2分するノードをもつ木の集合であり、データを追加したときに木の集合たるモデルを著しく複雑するデータを異常と判定する。