IIR輪講復習 #4 Index construction

お知らせ たつをさんによる補足情報 復習資料おきば http://chalow.net/clsearch.cgi?cat=IIR http://bloghackers.net/~naoya/iir/ppt/

参考 http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 本資料は書籍の輪読会に向けたサマリ 資料内で一部上記ドキュメントからの引用あり

4章のテーマ インデックス構築に関する実装面の話題 扱う手法 巨大なインデックスをどう構築するか 主にソートの話題 ハードウェアの制限とインデクシングアルゴリズムの関係 扱う手法 BSBI, SPIMI Distributed Indexing (MapReduce) Dynamic Indexing (logarythmic merging)

検索とハードウェア

検索システムとハードウェア 検索システムの構成はハードウェアの特徴に依存する 速度 ディスクは遅い、大きい メモリは速い、小さい メモリ: 5 x 10^-9 sec / byte ディスク: 2 x 10^-8 sec / byte

2007年における典型的な数字

ディスクの読み書き ヘッドのシーク時間が支配的 CPU処理とI/O処理のオーバーラップ ひとつの塊なら 10MB を 0.2 sec 隣接させて読み書きしよう CPU処理とI/O処理のオーバーラップ 圧縮して読み書きすると良い時がある

BSBI

インデックス作成時の問題点 インデックス作成 term, docID ペアを集める docID → postings list として組織化 巨大だとメモリだけでは処理できない → ディスクI/Oが発生するため遅い

ディスクを使うなら 外部ソート ソート中のランダムなディスクのシーク回数を最小化する なるべくシーケンシャルに読む

BSBI blocked sort-based indexing コレクションを等しいサイズに分割 各断片の termID, docIDs ペアをインメモリでソート (単語 → termID のマッピングが必要) 中間のソート結果をディスク上に保存 最後に中間ファイルをマージ

BSBI

BSBIのポイント メモリブロックでディスクI/Oを最適化 ディスクのブロックサイズと同じ(もしくは整数倍) の固定サイズのメモリブロックに結果を書き出す メモリブロックが一杯になったらディスクに中間ファイルとして出力 新しいメモリブロックを用意 最後に中間ファイルをマージ 優先度付きキューなどを使うと良い。

BSBIの図

BSBIの複雑度 Θ(T log T) ソート処理に依存 ただし、全体の処理は PARSENEXTBLOCK と最後のマージ (MERGEBLOCKS) が支配的

SPIMI

BSBIの欠点 単語 → termID マップが必要 巨大なコレクションではこのマップがメモリにフィットしない

SPIMI single-pass in-memory indexing ディスク容量が許す限りどんなサイズでもインデクシングできる termID は使わない term, docID ペアをストリームで処理 ブロック毎に辞書も書き込む ディスク容量が許す限りどんなサイズでもインデクシングできる

SPIMI

SPIMI のポイント BSBI と前処理、後処理は似ている BSBI が termID, docID ペア全体をインメモリで扱うのに対し、SPIMI は term, docID をストリームで 各postings list のサイズは最初には見積もることができない → 足りなくなったら倍々に増やす

BSBI と SPIMI の違い SPIMI は a posting を postings list に直接追加する ソートがないため高速 termID が必要ないのでメモリを節約できる 単一のブロックでの処理比較は SPIMI の方が効率が良い

SPIMI の複雑度 Θ(T) BSBI は Θ(T log T) ソートが要らない ほとんどのオペレーションがコレクションサイズに対して線形

Distributed Indexing

分散インデックス WWW検索規模などでは、インデクス構築は単一マシンでは時間、サイズともに実現が難しい 計算機クラスタでのインデクス構築 ∴ 分散インデックス

partitioned index インデックス全体を docID か termID のどちらかを軸に分割する term partitioned index, document partitioned index

MapReduce Google の分散インデックス構築システム 計算機クラスタによる並列計算 並列計算をするための分散ハードウェア環境と、ソフトウェア環境 コモディティなマシンで構成 「100 ~ 1000台」 計算途中でノードが壊れても自律的に復旧

Map と Reduce マスタノードがワーカー群に指示 ワーカーの役割 Map Reduce ワーカーはどちらにでもなり得る

Map key, value ペアを別の key, value ペアにする {docID, 文書}, {docID, 文書} ... → {term, docID}, {term, docID}, {term, doc} ... できあがった key, value ペアは中間ファイル”群” (segment files) として保存する ファイル1 a-f: {apple => 1}, {apple => 2} ... ファイル2 g-p: {hatena => 1}, {naoya => 2} ... ファイル3 q-z: {tatuwo => 5}, { unix => 5} ...

Reduce Map がはき出した sefment files から、同じ key の key, value ペアを集めて所望の出力を作る {“apple”, 1}, {“apple”, 5}, {“apple”, 6} → apple => [1, 5, 6] (すなわち term => postings list)

マスタノード Map や Reduce を実行するノードを管理 与えられた入力を断片に分割、これを空いているなワーカーに振り分ける 中間ファイルはネットワークI/Oを最小化するため、Map ノードのローカルに。

MapReduce

MapReduce ほか 完成した分散インデックスからの検索 document partitioned index フロントエンドから複数の検索サーバーに並行して問い合わせて、結果をマージする document partitioned index term partitioned index を document partitioned index に変換するのも MapReduce の役割 MapReduce は汎用的な並列計算クラスタ MapReduce のアーキテクチャに適合する多用な問題を解くことができる

Dynamic Indexing

Dynamic Indexing 更新があまりないドキュメント群 更新が多いドキュメント群 スクラッチからインデックスを作り直す スクラッチからビルド? Dynamic Indexing 補助インデックス + メインインデックス

補助インデックス + メインデックス 補助インデックス 補助インデックスが追加によって大きくなりすぎたら、メインインデックスへマージ インメモリ、追加可能 検索は両方のインデックスに行い、マージ 削除は Invalidation bit vector + フィルタ 更新 = 削除 + 追加 補助インデックスが追加によって大きくなりすぎたら、メインインデックスへマージ

インデックスのマージ マージのコスト: インデックスの保存形態に依存 各 postings list 毎にファイル: ○ マージは簡単 × ファイルシステムは大量のファイルを効率的に扱うことができない postings list を一つのファイルに × マージが大変 ○ postings list が大量になっても処理できる

Logarithmic merging マージ T/n 個の posting をマージ → Θ(T^2 / 2) T postings の合計数 Logarithmic merging アルゴリズム Θ(T^2/n) → log( T log(T/n) )

Logarithmic merging

Logarithmic merging n個の postings を扱うインメモリのインデックス Z0 Z0 が一杯 → ディスク上に 2^0 * n 個の I0 次に Z0 が一杯 → 2^1 x n 個の Z1 Z0 + I0 → Z1 Z1 I1 がなければ I1 としてソート I1 があったら Z2 にマージ ... (繰り返し)

複数インデックスの欠点 正確な統計情報が単純な探索では分からなくなる (検索ヒット数など) スペル訂正アルゴリズム、ranked retrieval などに影響 実際の Dynamic Indexing はもっと複雑 大きなサーチエンジンではスクラッチからの再構築が使われることも多い 最近は Dynamic Indexing も?

まとめ 検索システムの設計は対象のドキュメント群のサイズとハードウェアの性質に依存 ドキュメントが少い → 力業でシンプルに メモリとディスクの性能のギャップ ドキュメントが少い → 力業でシンプルに 多少多くても単一マシンで処理できる程度 → BSBI や SPIMI が有効 複数サーバーが必要とされるような大規模な問題となるとパラダイムが変わる。MapReduce。 別の軸の問題として、インデックスの再構築問題がある 定期的なスクラッチからの再構築 Dynamic Indexing