第10回MG輪講: 5章 Index Construction

IR MG

第10回MG輪講に参加してきました．13:00-19:00の長丁場でした．

内容が盛りだくさんだったので，帰宅してから復習がてらに学んだ内容をまとめてみました．やっぱりもりだくさんという事実と，参加者以外には到底理解できないであろうまとめノートが出来上がりました．


目次はこんな感じ．長い．

  • 5. Index construction
    • 5.1 Memory-based inversion
    • 5.2 Sort-based inversion
    • 5.3 Exploiting index compression
    • 5.4 Compressed in-memory inversion
    • 5.5 Comparison of inversion methods
    • 5.6 Constructing signature files and bitmaps
    • 5.7 Dynamic collections


本章は大きく三つに分けられる．

  1. インデクス構築方法
    1. メモリを使ったナイーブな方法
    2. sort-based手法
    3. compressed in-memory手法
  2. シグネチャファイルとビットマップインデクスを虐める会パート2
  3. 動的インデクスについて一言

最初のインデクス構築方法がメイン．これに色々な手法が紹介されている．モチベーションとしては，メモリに乗り切らない場合の対処方法の紹介．


いかんせん1999年 (11年前!) の本なので，ちょっと時代を感じる台詞がところどころに現れる．

単純な方法ではメモリが4GBも必要になるのだ！!

メモリ4GBありますが何か? と突っ込みたくなる．いずれにせよ，小さい節約が大きな節約につながる場合もあるので，きちんと勉強しよう．


インデクス構築手法は以下のとおり，以下順番に説明していく．名称は本書のまま．

  • Linked lists (memory, disk)
  • Sort-based
  • Sort-based compressed
  • Sort-based multiway merge
  • Sort-based multiway in-place
  • In-memory compressed
  • Lexicon-based, no extra disk
  • Lexicon-based, extra disk
  • Text-based partition

Linked-lists (memory, disk)

その名のとおり，転置リストを線形リストを用いてメモリ上に構築していく方法．下記のイメージ．

cold -> 1:1 -> 4:1 -> NULL
days -> 3:1 -> 6:1 -> NULL
...

最も単純で，MGで紹介されている手法の中で最も速いが，消費メモリサイズも最大．
逐一ディスク上でやったら大変なことになってしまう．

Sort-based inversion

メモリに載る限り，単語IDのt，文書d，頻度f_{d,t}という三つ組タプルに落とし込んで，マージソートのように併合しながらソートしていく方法．


具体的には，一度にメモリに乗り切る程度のサイズのブロック (本書ではこのブロックをrunと呼ぶ) に分けて，run内でソート (e.g., クイックソート) を行い，ディスクに書き出す．書き出されたrunをディスクから読み込みながらマージソートによって併合していく．最終的には複数のrunはひとつのソート済みのタプル列になるので，これを元に転置インデクスに変換する．


Sort-based compressed

単純なsort-based inversionでは，大量のがディスクに読み書きされるため，ディスクI/Oがボトルネック (disk-intensive) になる．

そこでCPUを支配要因 (processor-intensive) になるように，というタプルを圧縮してからディスクに読み書きする．具体的にはひとつのRun内ではtによってソート済なので，tは必ず昇順になっている (同値含む) ．単語IDの差分を取ることによって0以上の値に変換することができ，この値はかなり小さいになると推測される．これをUnary符号化することで，圧縮を実現する．documentIDや，単語頻度をどのように圧縮するか，という部分はよくわからなかった．


Sort-based multiway merge

タプルを圧縮することにより，processor-intensiveになったため，今度はディスクI/Oを増やすことが可能になる．

そこで一度に2つのrunを併合するのではなく，複数のrunを併合する手法を思いつく．これがmultiway merge．

複数のソート済みリストをマージする問題と同じ．ヒープのようなpriority queueが必要となる．(この部分がなかなか理解できずに，輪講を中断させてしまった．．．)


Sort-based multiway in-place

上記と同様の手法．in-placeの名前のとおり，併合するrunを読み込みながら，読み終わったrunに書き込んで行くという方法．
当該runが完全に読み終わったかどうかを判断するためにfree-listという，終了情報を格納する配列を利用．


ディスク容量に制約がある場合でも利用可能というのがウリ．そういう割には，free-listが空の場合には，新しく容量を確保するので，必ずしもin-placeで実行可能とは限らない．


Compressed in-memory inversion

Large memory inversion

まず，説明のために圧縮を行わない場合の基本的な方法を述べてから圧縮手法について説明する．


単語tの文書頻度であるf_tと総文書数Nが既知の場合，各単語tに対して最大

f_t \times \lceil log N \rceil

サイズの転置リスト領域を確保すればよい．


compressed in-memory手法では基本的に2パスで行われる．最初のパスでは全ての単語についてf_tを求める．2番目のパスで，確保した転置リスト領域に書き込んでいく．


lexiconには，各単語について，

  1. 転置リスト領域の最初の位置
  2. 現在位置 (前回追加した最後の位置)

の二つの情報を格納しておく．


文書dの単語tがf_{d,t}回出現していたら，lexiconから単語tを引っ張り出して，現在位置にの情報を追記して現在位置を進める．

この際，最初のパスでf_tの正確な数字を求めているため，各単語の転置リスト領域を超えて書き込むことは絶対に起こらない．

今度は，転置リスト領域をゴロム符号によって圧縮することを考える．ゴロム符号はパラメータbの商と余りを符号化する圧縮アルゴリズムである．(詳細は割愛)

圧縮を行わない場合と同様に「各単語tに対する転置リストの上限値」を知る必要がある．3.3節で解説した平均符号長を最小化するb^Aの計算式 (p.120の(3.2)式) にしたがって求められたパラメータでは，あくまで平均符号長しかわからない．

今回は最悪符号長を最小化するパラメータb^Wを用いることで，転置リストの上限値を設定してインデクスを構築することが可能になる．

最終的には，b^Wで圧縮した転置リストを一度復号して，b^Aを使って符号化する．


Lexicon-based, no extra disk (extra disk)

全ての単語に対する転置リストがメモリに乗り切らない場合には，2パス目の部分を分割することで対処する．1つ目のアプローチは，単語によって分割する方法である．

単語単位でデータを分割して，処理可能な単語群に対してメモリ上でインデクスを構築する．構築し終わったインデクスはディスクに書き出される．単語ごとに分割しているので，追記する形でディスクに書き込むことができる．

ただし，分割した回数だけ文書を読み込む必要がある．i.e., 単語を10分割したら，同じ文書に対して10回読み込みをかけなければいけないということ．


Text-based partition

2つ目のアプローチは，文書によって分割する方法である．
文書単位で分割して，処理可能な文書群に対してメモリ上でインデクスを構築する．

単語ごとの分割と異なり，同じ文書を何度も読み込む必要はなくなるが，分割されたそれぞれの文書群に対して，またf_tを求める必要があるので，3パス操作となる．

処理が終わったら，メモリ上に構築された転置インデクスをディスクに書き出す．この際，単語分割とは異なり，各単語に対応する転置リストに追記する形になるが，1パス目にf_tの値が分かっているので，ディスク上に各単語に対する転置リストの上限容量を確保することができる．



5.5 Comparison of inversion methods

インデクス構築方法のまとめ

  • sort-based methodsは1パスで済む
  • ここで紹介した方法は，あくまで大規模データに対する転置インデクスの構築方法
    • データがメモリに乗り切る場合には，メモリ上でやってしまえばいいので
  • いろいろ紹介したのは

5.6 Constructing signature files and bitmaps

おかえりシグネチャファイルとビットマップファイル．そしてさようなら．

  • ハッシュ関数の計算が一番時間コストに影響を与える
  • シグネチャファイル構築のためには，平均文書長と総インデクスポインタの数が必要になるので，実測値を用いる場合には否が応でも2パス構築になる．
  • bitmapインデクスを作る最良の方法は，圧縮転置インデクスを構築してからunary符号に変換することだったりする．
  • まぁ，使いたいとは思わないよね．で締めくくられている

5.7 Dynamic collections

動的にインデクスを構築する方法．大きく分けて二つの要件に分けられる

  1. 新しい文書の追加に対応
  2. 上記に加えてインデクスに含まれる文書の編集や削除にも対応
  • 各単語に対して "別刷り" インデクス ("stop-press") を用意して，追加情報はそちらに追記．別刷りインデクスが大きくなったら，転置インデクスと併合する
  • 現在のlexiconに含まれていない単語が出現する可能性があるので，完全最小ハッシュによるlexisonの検索を用いることができない．

インデクス構築方法について補足

MGではカバーされていないけれど，最近ではマージベースのインデクス構築方法が主流になっているらしい．これについては，山田浩之さんの「検索エンジンはいかにして動くのか？」[1]で次回紹介されるとのこと．要チェック!

日本語文献としては，同じく山田さんの研究会論文[2]にマージベースのインデクス構築法の既存研究が詳しく紹介されている．


まとめ

長くて大変でしたが，これくらい一度にやると，かなり勉強した気になります．ところどころの議論で知らなかったことが浮き彫りになるので毎度勉強になります．

次回からはしばらくテキストとは離れて画像の話題になります．今までは事前知識があったのでついていけた部分がありますが，今度からは予習をしっかりしないといけません．

今回少し話題にあがったのですが，本書であまり触れられていない辞書 (lexicon) の検索方法については後日まとめたいと思っています．

参加者のみなさまお疲れ様でしたー．


Reference