WEB Crawler(Chapter9)

WEB Crawlerとは？

新しくWEBにアップロードされたコンテンツを探すために用いられる
- WEB page, 画像，動画，PDFなど
使用目的は？
- サーチエンジンのindexing
  - 一番多い使用例
- WEB Archiving
  - 将来的に使うかもしれないデータを収集して保存する
- WEB Mining
  - 経済分析などに使用される
- WEB Monitoring
  - 海賊版検知

Framework

Step1: 課題理解，スコープ定義

基本的なアルゴリズムはシンプル
- 与えられたURLの集合からWEBページを全てダウンロードする
- WEBページからURLを抽出する
- 抽出したURLからWEBページを全てダウンロードする
- 上記を繰り返す

一見単純に見えるが，スケーラブルなクローラーを設計するのは大変

質疑応答

要件の理解と明確化を行う

クローラーの主目的は？
- サーチエンジンにおけるindexingのため
1月あたりどれくらいのWEBページを収集する？
- 1 billion pages
コンテンツの種類はどんなのがある？
- HTMLのみ
WEBページが追加/編集される場合を考慮する必要がある？
- はい．どちらも
WEBからクロールされたHTMLページは貯める必要がある？
- 最長5年
重複しているコンテンツはどう扱う？
- 無視してかまわない

WEBクローラーの設計で大切な観点

Scalability
- WEBは巨大なので，並列化などを用いながら効率的にする必要がある
Robustness
- BAD HTML，応答がないサーバ，間違っているリンクなど落とし穴がたくさん存在する．これらにも対応できる必要がある
Politeness
- 短時間で大量のリクエストを送ってはいけない
Extensibility
- 新しい種類のコンテンツに小規模の変更で対応可能でないといけない．

フェルミ推定

Step2:基本設計

Step1で明確にした要件を基に基本設計をする

以下では，各構成要素についてみていく

Seed URLs

いわばエントリーポイント．例えば大学のWEBサイトを設定するのが直感的かも．

URL Frontier

HTML Downloader

DNS Resolver

Content Parser

Content Seen?

Content Strage

URL Extractor

URL Filter

URL Seen?

URL Storage

WEB crawler workflow

Step3:詳細設計

議論する項目

DFS vs BFS
URL frontier
HTML Downloader
Robustness
Extensibility
Detect and avoid problematic content

DFS vs BFS

URL frontier

Politeness

Priority

Freshness

Storage for URL frontier

HTML Downloader

Robots.txt

Performance optimization

1.Distributed crawl

2.Cache DNS Resolver

3.Locality

4.Short timeout

Robustness

Extensibility

Detect and avoid problematic content

1.Redundant content

2.Spider traps

3.Data noise

Step4:まとめ

Extra