Information Retrieval and Web Search まとめ(6): インデックス構築(2)

前回は、1つのマシンを使ったインデックス構築アルゴリズムである BSBI (Blocked sort-based indexing) と SPIMI (Single-pass in-memory indexing) を紹介した。今回は、分散インデキシングと動的インデキシングについて説明する。

分散インデキシング

Web スケールのインデキシングでは、分散コンピューティングクラスタが必要
Web 検索のデータセンター（Google, Bing, Baidu）では主にコモディティマシンを使用
データセンターは世界中に分散している
Google では〜100 万台のサーバ、 300 万プロセッサ・コアを使っていると予想されている（Gartner 2007）
1000 ノードの非フォールトトレラントシステムで、各ノードの稼働率が 99.9% のとき、システム全体の稼働率は何％か？
- 答え：37%。つまり 63% の時間は１つかそれ以上のサーバーはダウンしている
- 演習：100 万台のサーバーがある場合、1分間のあいだに障害が発生するサーバーの台数は？
分散インデキシング
- マスター (master) マシンが、インデキシングジョブを指揮する
  - 「安全」であると考えられるように維持する
- インデキシングを複数の並列タスクへと分割する
- マスターマシンは、タスクのプールからそれぞれのタスクをアイドル状態のマシンに割り当てる

2種類の並列タスクを使う
- パーサー (parsers): Map フェーズ
- インバーター (inverters): Reduce フェーズ
入力となる文書コレクションを、スプリット (split) に分割する
- スプリットは、文書集合のサブセット（BSBI/SPIMI におけるブロックに対応する）

マスターはアイドル状態のパーサーマシンにスプリットを割り当てる
パーサーは文書を1つずつ読み込み、 (termID, docID) ペアを出力する
パーサーはそのペアを j 個のパーティションに書き込む
- 各パーティションはタームの最初の文字の範囲で分けられる
- 例： a-f g-p q-z の範囲に分かれている場合、 j = 3

インデックス構築はただ一つのフェーズとして説明していた
もう1つのフェーズが考えられる
- ターム分割インデックス (term-partitioned index) を、文書分割インデックス (document-partitioned index) に変換するフェーズ
  - term-partitioned: 1台のマシンはタームの1つの範囲を扱う
  - document-partitioned: 1台のマシンは文書の1つの範囲を扱う
このあと Web のパートで議論するように、ほとんどの検索エンジンは文書分割 (document-partitioned) インデックスを使っている

以上のインデックス構築アルゴリズムは、 MapReduce の1つの具体例である
MapReduce (Dean and Ghemawat (2004)) はロバストで、概念的にはシンプルな分散コンピューティングフレームワーク
- 分散部分のコード以外は
彼らは Google インデキシングシステム (ca. 2002) を、それぞれが MapReduce で実装されている複数のフェーズからできていると書いている

ここまで、コレクションは静的なものであると仮定していた
- 時間経過に伴って、文書が入ってきて、インデックスに挿入する必要がある
- 文書は削除されたり更新されたりする
つまり、辞書やポスティングリストは更新できなければならない
- ポスティングリストを更新
- 新しいタームを辞書に追加

大きなメインインデックスを管理する
新しい文書は小さい補助インデックスに入れる
検索するときには両方のインデックスから検索し、結果をマージする
削除
- 削除された文書のビットベクトルを管理する
- このビットベクトルを使って、検索結果から削除済み文書をフィルタする
定期的に補助インデックスをメインインデックスにマージする
問題点
- 頻繁にマージが起こる
  - マージ中はパフォーマンスが低下する
対策として、ポスティングリストごとにファイルを分けておくと効率的にマージできる
- マージはポスティングリストに追記するだけ
- しかし、大量のファイルができるので OS にとっては負担になる
この講義ではインデックスは1つの大きなファルであると仮定
実際には、その中間のアプローチをとる
- ポスティングリストは複数に分割
- 長さ1のポスティングリストは1つのファイルに集める
- など

ログマージ (logarithmic merge) は、複数のインデックスを管理するアプローチで、それぞれのインデックスは、以前のものの2倍の大きさになる
- 各インデックスはあるサイズ n の2のべき乗の大きさになる
- n, 2n, 4n, 8n, ...
最も小さいインデックス Z0 をメモリ上にもつ
大きいインデックス (l0, l1, ...) はディスク上に置く
l0 がなかったら、Z0 のサイズが n を超えたら l0 としてディスクに書き出す
- l0 がすでにあったら、 l0 とマージして Z1 とする
l1 がなかったら、 Z1 を l1 としてディスクに書き出す
- l1 がすでにあったら、 l1 とマージして Z2 とする

シンプルなアプローチ（メインインデックス＋補助インデックス）では、マージの回数は T/n
- T はポスティングの総数
- n は補助インデックスのサイズ
- インデックス構築の最悪時間計算量は O(T^2/n)
  - 各ポスティングに対して T/n 回のマージが起こった場合
ログマージでは、各ポスティングがマージされる回数は最大でも O(log (T/n))
- しかし、クエリ処理は O(log (T/n)) 個のインデックスに対して行ってマージしないといけない
  - シンプルなアプローチでは O(1) だった（メインインデックス＋補助インデックスだけ）
さらに、コレクション横断の統計量を管理するのが大変
- たとえばスペル訂正とか
- これらは後で見るように、ランキング計算に必要