04 Index construction (1) (pp.61-67)

IIR

4章の前半1/3くらい読んだ．読む時間はだんだん速くなっているけれど，理解しているか確認しながらメモを取るとものすごい時間がかかってしまう．でも3日で忘れないためメモする．

今日学んだこと

  • hadware basics
  • blocked sort-based indexing (BSBI)
  • single-pass in-memory indexing (SPIMI)

4.1 Hardware basics

ハードウェアの基本をば

  • average seek time
  • transfer time per byte
  • processor's clock time
  • lowlevel operation
  • size of main memory
  • size of disk space

解説は深いところまで踏み込んでいない．以下の点に留意するべきらしい

  • メモリアクセスはディスクアクセスより速いよ．できるだけデータはメモリに載せませう
  • ディスクのread, writeする場合はできるだけ一塊が大きいデータを扱いませう
    • シークの間は何もできないから，細切れのデータとか最悪
  • OS（と書いてあるけれどファイルシステムでなくて？）は基本的にブロック単位でファイルを扱う
    • ブロック単位より小さいファイルの読み書きにはブロックと同じ時間がかかる
  • ディスクからメモリに読み込むのにはシステムバスが使用される．システムバスはCPUとは異なるので，これらは並列に処理することができる．
    • なのでuncompress dataを読み込んでdecompressする方が，uncompressed dataを読み込んで処理するより速い

4.2 Blocked sort-based indexing

ここからはnonpositional indexのハナシ．nonpositional indexは以下の流れで構築される

  1. 文書群からすべてのterm-docIDペアを作成する
  2. termをキーにしてsortする
  3. postings listはdocIDをkeyにしてsortする

termからtermIDにmapするのはon the flyで処理するsingle passとtwo-passの二通りがあるけれど，本書ではsingle passらしい．深く考えないでおく．


blocked sort-based indexing (BSBI) は，メモリにのっかりきらないからディスクを使おうというスタート地点

  1. 文書群を等分割する
  2. メモリ上でtermID-docIDをソートする
  3. ソートされた中間ファイルをディスクに格納する
  4. すべての中間ファイルをマージする

最後のマージはマージソートなんだろうな．

p.66 beefy（=太った）という単語にちょっと笑った

4.3 Single-pass in-memory indexing

BSBIの問題点はterm->termIDのマッピングをしなければいけないということ．termはそのままでいいじゃん，という発想からSingle-pass in-memory indexing (SPIMI) が出てくる．

BSBIとの違いは，postings listにpostingをダイレクトに追加するというもの．termID-docID pairsを作成してからマージするBSBIとは違い，動的にposting listに追加していく．

メモリがいっぱいになるまで，dictionaryにterm-docIDを追加していって，メモリがいっぱいになったらdictionaryをsortしてからディスクに書き出す．

最後にBSBIと同様にマージする


利点はふたつ

  1. 速い：ソートがないから
  2. 省メモリ：termIDではなくtermのpostings listを直接持ってるから（ほんと？）

postings listに対するメモリは適当にallocateしておいて，足りなくなったら2倍に増やしてあげる．



4.4 Distributed indexing以降はまだ読んでいない．