ソートされたシーケンスの直積を高速に求めるアルゴリズム 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分するノードをもつ木の集合であり、データを追加したときに木の集合たるモデルを著しく複雑するデータを異常と判定する。
1972年に発表されたB木のオリジナルの論文。 \(I\)をインデックスの大きさ、\(k\)をハードウェア依存の値とすると、検索、挿入、削除の時間計算量は\(\log_kI\)になる。 ここでのインデックスは、固定長の\((x, \alpha)\)を要素とする連想配列で、最大\(2k\)個のキーを格納できる連続するページ上にある。 \(\alpha\)には、たいてい1つ以上のレコードへのポインタが格納される。
ハッシュコーディングで要素がハッシュエリアにあるかを高速に調べる手法で、ブルームフィルタの名で知られる。 偽陽性を認めることで、ハッシュ値の保持に必要なハッシュエリアを小さくしているため、ハッシュエリアが大きくなるデータでも利用することができる。 例えば、データベースのストレージで使われており、検索するキーがデータベースに存在するか事前に確かめることで、存在しないキーのための不要なディスクの読み取りを省くことができる。 なお、偽陰性の誤りはない。
SSDのランダムな書き込みを高速化するために、インデックスにつかうデータ構造FD-treeを提案した。 FD-treeのエントリ数が\(n\)でページサイズが\(B\)のとき、ランダムな読み込みと書き込みの計算量はともに\(\mathcal{O}(\log_B(n))\)になる。
Isolation Forestは、完全二分木による異常検知の手法で、iForestともよばれる。時間計算量が線形で、ハイパーパラメタがわずか2つで、メモリ効率がよい。 時間、空間計算量が少なく高次元のデータに向く。