stop-the-world

takuya-a のブログ

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

前回はフレーズクエリと位置インデックスについて説明した。今回は、基本的なインデックス構築と、外部メモリ（＝ストレージ）を使ったインデキシングについて紹介する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の5日目の記事です。

adventar.org

基本的なインデックス構築の流れ

2日目の記事（転置インデックス）では、簡単な転置インデックスの構築方法を解説した。だが、メインメモリのサイズには上限がある。その上でどのように大きなインデックスを構築すればいいだろうか。

  • (1) すべての文書をパースし、単語を抽出し、文書 ID (docID) とともに保存する
    • Doc 1: "I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me."
    • Doc 2: "So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious"
Term      docID
I             1
did           1
enact         1
julius        1
caesar        1
I             1
...
brutus        1
killed        1
me            1
so            2
let           2
it            2
be            2
with          2
caesar        2
...
was           2
ambitious     2
  • (2) すべての文書のパースが終わったら、転置ファイルをタームの辞書順でソートする
    • 以後、このソートステップに注目する
Term      docID
ambitious     2
be            2
brutus        1
brutus        2
capitol       1
caesar        1
caesar        2
caesar        2
did           1
enact         1
...
was           1
was           2
with          2

Reuters-RCV1 コレクション

  • Reuters のニュース記事1年分（1995-1996）のコレクションを使う
    • それほど大規模なわけではないが、公開データセットとしてはそれなりのサイズ

f:id:takuya-a:20201205224329p:plain
Reuters-RCV1 に含まれるニュース記事

  • Reuters-RCV1 の統計情報のサマリは以下の通り

f:id:takuya-a:20201205224428p:plain
(IIR p.70 Table 4.2) Reuters-RCV1 の統計情報。ユニークターム数は 391,523、全トークン数は 96,969,056。タームの平均サイズは 7.5 バイト、トークンの平均サイズは 4.5 バイト。

ソートベースのインデックス構築

  • インデックスの構築中は、文書を1つずつパースしていく
    • 最後の文書までパースしないと最終的なポスティングリストは確定できない
  • 単語ごとに (termID, docID) のペアを保存しなければならない
    • それぞれ 4 バイトと仮定（合計 8 バイト）
  • Reuters-RCV1 では全トークン数が 100M くらいあるので、それだけで 800 MB のスペースが必要
    • 今日のコンピュータでは実行可能だが、典型的なコレクションはもっと大きい
    • 例： New York Times は 150 年分以上のニュース記事のインデックスを提供している
  • なので、中間結果をディスクに保存する必要がある
    • インメモリのインデックス構築ではスケールしない

ハードウェアの基本

  • 検索システムに使われるサーバは通常、数〜数十GBのメインメモリをもつ
  • ディスクサイズはその数十〜数百倍
  • メインメモリへのアクセスは、ディスクに比べてはるかに速い
  • ディスクシークの間はデータが転送できない
    • つまり、小さなデータをたくさん転送するより、1つの大きなデータを転送したほうが速い
  • ディスクIOはブロックベース
  • ブロックサイズは 8 KB ~ 256 KB
  • そのため、ディスク上でソートするのは非現実的
    • 大量のディスクシークが発生するため、とても遅い
    • 外部メモリを使った別のソートアルゴリズムが必要

f:id:takuya-a:20201205224638p:plain
(IIR p.68 Table 4.1) 2007年頃のハードウェアのパフォーマンス

BSBI (Blocked sort-based indexing)

  • BSBI (Blocked sort-based indexing) は、外部メモリを使ったインデキシング方法
  • 各レコード (termID, docID) (8バイト) を 1000 万個（10 M）くらいまでのまとまり（ブロック）に分ける
    • 全レコード数は約 1 億個 (100 M) なので、10 ブロックに分割される
  • 基本的なアイデア
    • ブロックごとにポスティングを集めてソートし、ディスクに書き出す
    • そのあと、それらのブロックをソート順を保ちながらマージする

BSBI のアルゴリズム

f:id:takuya-a:20201205224742p:plain
(IIR p.71 Figure 4.2) BSBI のアルゴリズム

  • ブロックを読み込み、その中のレコードをソートし、ディスクに書き出す
  • 10 ブロックを2つずつマージしていく
    • (1, 2) (3, 4) (5, 6) (7, 8) (9, 10) というふうにマージ
    • 次は (1, 2) と (3, 4) をマージ……というふうに続ける
    • マージツリーは log2 10 = 4 階層になる
    • マージした結果はまたディスクに書き出す

f:id:takuya-a:20201205224828p:plain
(IIR p.72 Figure 4.3) BSBI のマージ処理

  • しかし、すべてのブロックを同時に読み込みながらマージするマルチウェイマージ (multi-way merge) のほうが効率的
    • すべてのブロックのファイルを同時に開く (open)
      • それぞれのブロックごとに読み込みバッファを作って管理
    • 各イテレーションでは、最も小さい termID を1つ選ぶ
      • この termID は優先度付きキューを使って選択する
    • 選んだ termID に関するすべてのポスティングリストをマージして、出力ファイルに書き出す
  • 読み込み・書き出しのためのバッファのサイズを適切にしていれば、ディスクシークで死ぬことはない
  • 残っている問題
    • 辞書はメインメモリに収まることを仮定している
    • タームから termID にマッピングするために、動的に追加できる辞書 (term-termID mapping) が必要

SPIMI (Single-pass in-memory indexing)

SPIMI のアルゴリズム

  • ドキュメントはパースされ、その結果はトークン (term-docID ペア) のストリームとして扱われる
  • トークンストリームごとに以下の SPIMI-INVERT が呼び出される

f:id:takuya-a:20201205224904p:plain
(IIR p.73 Figure 4.4) SPIMI のアルゴリズム。ブロックから転置インデックスを作成し、ファイルに書き出す。

  • SPIMI は BSBI と違ってポスティングリストにポスティングが直接追加される (L10)
    • BSBI では最初にすべての termID-docID ペアを集めてからソートしていた
    • そのため、 SPIMI ではポスティングリストは動的に拡張される
    • ソートが不要になるので高速
    • ポスティングリストが属しているタームを管理しなくてよいのでメモリ消費量が少ない
  • 圧縮を使うことで SPIMI をさらに効率的にできる
    • タームの圧縮
    • ポスティングの圧縮
  • 圧縮については次回以降で扱う
    • IIR chapter 5

講義資料

参考資料