読者です 読者をやめる 読者になる 読者になる

IIR4章まとめ

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つのファイルに書き込むと、マージは大変だが、インデキシングの効率はよい。