4章は、インデックス構築について。ハードウェアにも言及した、実用上の構築アルゴリズムを説明している。
BSBI(Blocked Sort-Based Indexing)
インデックスは巨大でありメモリには載っかりきらないので、ディスクを使うことにする。
アルゴリズムは以下。
①ドキュメントセットを等分割。
②分割されたそれぞれでタームid-ドキュメントidをソートする。
③ソートされた中間ファイルをディスク上に保存する。
④全ての中間ファイルをマージする。
SPIMI(Single-Pass In-Memory Indexing)
BSBIでは、ターム→タームidのマッピングうをしなければならない。
このマッピングはサイズが非常大きくなり、コストがかかる。
そこで、タームidを用いずにターム-ドキュメントidというペアを作り、動的に追加していく。
BSBIと比べて速く、メモリ効率がよい。
分散インデックス(MapReduce)
Webスケールなどの大規模なインデキシングには、複数のコンピュータが必要。
以下にデータフローを示す。
- master
空いているperserにsplitsを、空いているinverterにsegment filesを割り当てる。
- parser
ドキュメントを読み込み、ターム-ドキュメントidのペアを編集する。
頭文字によりj個に分割された部分にそれらを書き込む。(上図の場合はj=3)
- inverter
ターム-ドキュメントidのペアを部分ごとに集め、ソートしてpostingsに書き込む。
動的インデックス
上記では、ドキュメントセットは静的として話を進めてきたが、実際にはドキュメントの挿入・削除・変更などが行われ、動的にドキュメントセットが変更される。
基本的なアイデアとしては、インデックスをメインインデックスと補助インデックスに分ける。
- 検索は両方のインデックスに対して行い、結果をマージする。
- 定期的に、補助インデックスをメインインデックスにマージする。
マージの容易さとインデキシングの効率はトレードオフ
- postingsごとにファイルを分けると、マージは容易だが、多くのファイルが必要になり効率的ではない。
- postingsを1つのファイルに書き込むと、マージは大変だが、インデキシングの効率はよい。
