Introduction to Information Retrieval #4 の復習資料

Introduction to Information Retrieval の4章の復習資料を以下にアップロードしました。

• http://bloghackers.net/~naoya/iir/ppt/iir_04.ppt

4章はインデックス構築に関するアルゴリズムなどがテーマです。

前半では単一マシン上で二次記憶装置を使ったインデックス構築手法として、入力を適当なサイズのブロックに分けて最後にマージする Blocked sort-based indexing (BSBI) と、BSBI を改良して入力をストリームで扱うようにした Single-pass in-memory indexing (SPIMI) が紹介されています。

次に、例えばウェブ検索のような、単一のマシンでは扱いきれない巨大なインデックスを扱う戦略として、並列計算クラスタで分散インデックスを構築する Google の MapReduce が紹介されています。最後はインデックス更新を動的に行うための Dynamic indexing、その要素技術としての Logaryithmic merging についての解説があります。

次回の輪読会は 5/17 予定です。復習資料のアップロードも 5 月になります。内容は、インデックスにおける辞書や postings list の圧縮についてです。5章はかなり面白かったです。

過去の章のアーカイブは同 URL のディレクトリ (http://bloghackers.net/~naoya/iir/ppt/) から一覧できます。現在、都合により 3章の後半の復習資料が抜けています。次回輪読会以降にアップロードしたいと思います。