20.1 ウェブクローリング
ウェブの世界からページを集め，それらをインデックス付し検索エンジンの手助けをするプロセス
- できるだけ有用なページを集める
- それらを結んで切るリンク情報を共に収集する
- 高速に，効率的に集める
20.1.1 クローラが提供すべき機能
頑健性 (robustness)
スパイダートラップ
=> クローラをだましてある特定のドメインから無数のページを取り出させるように仕向けるウェブページ
クローラはこのようなわなに対して体制を持たなければならない
礼儀正しさ (politeness)
Webサーバはクローラがウェブサイトを訪問する比率を制御する暗示的，明示的なポリシーをもっており，これらは尊重されなければならない
20.1.2 クローラが提供すべき機能
分散性
クローラは複数の機会をまたがって分散された形で実行できるべきである
スケーラビリティ
クローラはマシンや帯域幅の追加によりスケールアップ可能であるべきである
性能と効率
クローラはプロセッサ、ストレージ、ネットワークなど様々なシステム資源を効率的に使うべきである
新鮮さ
クローラは連続性を保証する，つまり以前に獲得したページを更新することで最新の状態を保たなければならない．
クローラはページの更新頻度に近い形でページをクロールできるべきである
拡張性
新しいデータ形式や新しいプロトコルにも対応できなくてはならない．
20.2 クローリング
- あるホストに対してはただひとつのコネクションが開かれるべきである
- 一つのホストへの連続したリクエストは何秒か間を置くべきである
- 20.2.1に示す礼儀正しさには従うべきである
20.2.1 クローラのアーキテクチャ
URL Frontier
クロール対象のリンクが格納されている
- URL FrontierからひとつのURLと取り出す
- httpプロトコルを用いてウェブページを取ってくる
- 言語解析により，テキストとリンクを取り出す
- 各リンクをURL Frontierに格納するかをきめる
URL Frontierに格納するかの決定
- すでにクローラによって確認されたページか？
- URLフィルター
- 特定ドメインの排除
- robots.txt の確認
- すでにURL Frontierに存在しないか？
クローラを分散する
どのように分散クローラはURLを共有するか？
20.2.2 DNS解決
まぁいまの時代ほとんど必要ないよね…
20.2.3 URL Frontier
URLにどのように優先順位をつけるか？
- 頻繁に更新される高品質のページはよくクロールされるべき
- 礼儀正しさ
目的
- どのホストに対してもコネクションはひとつだけ
- コネクションから引き継いだ次のリクエストには待ち時間がある
- 優先順位の高いページは選択的にクロールされる
フロントキューで優先順位を，バックキューで礼儀正しさを実装する
フロントキュー
F個ある
URLに1-Fの優先順位をこれまでの経過にもとづいて割り当て
i番目の優先順位を得た場合はi番目のキューに格納する
バックキュ−
- 空ではない
- 一つのホストからのURLだけを含む
- ヒープを用いて待ち時間を管理する
20.3 インデックスの分散化
用語での分割で大域的インデックス構造をとる
辞書が部分集合に分割され、各々の部分集合がノードに配置される．
クエリはそのクエリ用語に相当するノードに回される．
大きな並列性が可能になる．
実際には難しい．
複数の語からなるクエリでは大きなマージを行わなければならない可能性がある．
共起性をもとにどの語をどのノードに分割するかが重要になる．
文書での分割で局所的インデックス構造をとる
一般的な実装
各ノードは全文書の部分集合に対するインデックスをもつ
各クエリはいろいろなノードにおくられ、その結果をマージしてユーザに返す
どのように分割するべきか．
ひとつの考え方として同一のホスト由来の文書を同一のノードに振り分ける
20.4 接続サーバ
- どのURLがどのURLにリンクしているか
- どのURLがどのURLからリンクされているか
をウェブグラフを構築するために保存・運用する必要がある
ウェブの世界に40億のページがあり，その各々が10個のリンクをもつと仮定する．
各リンクの両端点を表すのに32ビット必要になると考える．
4 * 10^9 * 10 * 8 = 3.2 * 10^11 バイトのメモリが必要になる
リスト感の類似性
表の中野多くの行は，多くの共通の要素を持っているためにいくつかの行をつかって簡潔に表現できる
局所性
すぐ近くのページをしているので，小さい整数を用いてコード化できおる
ソートされたリストのなかでギャップのコード化を行う
その前の要素からのオフセットをもつ