04 Index construction (3) (pp.72-77)
ようやく4章読了．logarithmic mergingをやっと理解．理解すると簡単なことに気がつく．英語で理解できない->日本語の解説を探す，という悪癖が徐々に直ってきた．逃げちゃだめだ逃げちゃだめだ．
ただし，floor(T/n)回処理しなければいけないという部分だけ理解できず．
4.5 Dynamic indexing
- dynamic indexingは複雑なんで，大規模の検索エンジンは最初から作り直す場合がある
- binomial heap structureと同じ考え方らしい (Cormen et al. 1990を参考)
4.6 Ohter types of indexes
- 本章では位置情報を持たない転値インデックスのみを扱っていた
- position dataを持たせても今まで解説したアルゴリズムは基本的に適用可能
- postings listをdocIDでソートしているのは，docIDの代わりにdocIDの差分を取るときに便利
- postings listは通常docIDでソートする
- 文書の追加が楽
- 検索結果をランクづけする場合，weightやimpactスコア順にpostings listをもたせることも
- 文書の追加が面倒
