クローラの種別

5.2 WISDOMのクローラ 37

5.2.2.2 _{更新クローラ}

更新クローラは，URL DBに登録されたURLのうち，既に取得済のページについて更新されていな いかを確認するために，定期的に再クロールする．Webページは日々更新されるため，収集した時点で 最新であるページも時間の経過とともにその情報は古くなる．十分に短い間隔で再クロールをおこなうこ とで全てのページを最新の状態に保つことは可能であるが，クロールの資源は有限であるためいかに少な いクロール資源で収集データを最新の状態に保つかが問題となる．

一般に，効率よくWebページを最新の状態に保つためには，各Webページの更新間隔にあわせて再ク ロールをスケジュールすることが求められる．ここで，問題は2つに分解できる．すなわち，Webペー ジの更新間隔を推定する問題と，推定された更新間隔に基づいて再クロールをスケジュールする問題であ る．以下に，WISDOMの更新クローラで取られているアプローチについて述べる．

まず，Webページの更新間隔の推定について，Webページの更新が指数分布に従うと仮定する．すな わち，最終クロール時刻tcrawlのページが時刻tにおいて更新されている確率は，

β(t,tcrawl) = 1−exp

"

−t−tcrawl

τ

#

(5.2) となる．ただし，τ はページの推定更新間隔である．ページpについて更新がn回観測され，それぞれの 更新の間隔がxiとすると，最尤推定をするとτ は観測された更新間隔の平均となることが分かる．

τ =1 n

%ⁿ

i=1xi (5.3)

更新クローラでは更新されたという情報以外に，再クロールして更新されていなかった場合に，最終更 新時刻から再クロールした時刻までの間に更新されていなかったという情報が利用できる．この情報を利 用して得られる補正平均更新間隔τ^∗は次式で与えられる．

τ^∗=τ+tcrawl−tlast

n (n>0) (5.4)

ここで，tlastは最終更新時刻である．観測数nが小さいときにはτ の信頼度が低く，特にτ が過小に推 定された場合には更新されていないページを無駄に再クロールしてクロール資源を浪費することになる．

上記の補正をおこなうことにより，ある程度はこの問題を回避することが出来る．

上記の更新間隔推定には，観測した全ての更新について記録は必要なく，十分統計量である更新間隔の 平均τ，更新回数n，および補正平均更新間隔を算出するのに必要な最終更新時刻tlast，最終クロール時

刻tcrawlのみを記録しておけばよい．ページあたりに保持が必要な情報量が小さく，管理するページの量

が大規模な場合に向いている．各種推定値は，時刻tでページの更新を観測したとして，次のように更新 する．

t^$_crawl=t (5.5)

t^$_last=

&

LastModified (LastModifiedが利用可能の時) t (それ以外の時)

τ^$= τ n+t^$_last−tlast

n+ 1 n^$=n+ 1

5.2 WISDOMのクローラ 39 更新クローラにおける再クロールのスケジューリングは，新規クローラと同様，確率的に収集対象を選 択することにより実現する．具体的には， (2)式で与えられる更新確率を用いて，選択確率を以下のよう に表現する．

γ(t,tcrawl) =ω(α(λ) + (1−α(λ))β(t,tcrawl)) (5.6) ここで，α(λ)はページの重要度λを変数とする関数で値域は[0, 1]であり，ωは減衰率である．更新ク ローラではURL DBから収集済みページをスキャンして，5.6式で求められる確率に基づき一定件数（〜

数100万件）ずつ選択し更新クロールを実施する．ωはURL DBから収集対象としての選択されやすさ を表すパラメータである．URL DBをスキャンして収集対象を選択するという方法をとっているため，

URL DB上のページの偏りから収集対象が偏る現象が起きる．ωで選択確率全体を低く抑えることによ

り，URL DB全体から広く薄く収集対象が選択されるようにしている．現在の運用ではα(λ)=0.005，

ω=0.5という値で運用している．

5.2.2.3 深度クローラ

Web情報分析にとって，ニュースサイトは重要な情報源の一つである．深度クローラはニュースサイ トなど，定常的に価値の高いページが発信されるサイトを定期的クロールし，質の高いページを効率よく 収集するためのクローラである．深度クローラでは起点となるページのURLと深度dの対を入力として とる．深度クローラは一定間隔毎に起動され，まずは起点となるページを収集する．起点となるページか ら抽出されたリンクについて，収集済みのものを除いた上で，深度をd-1にして，収集対象リストに追加 し，クロールを継続する．この処理を深度が1以上のページがなくなるまで繰り返す．

図5.4に深度クローラによるクロールの例を示す．ここでは，起点としてhttp://www.news-site.com/

というURLが深度3で登録されている(図中(a))とする．(a)には(b)および(c)へのリンクがあるの で，深度クローラは(b)および(c)を深度2でクロールする．さらに(b)には(d)へのリンクがあり，(d) は深度1でクロールされる．(d)のさらに下位のページ(e)にたどり着き深度でクロールされた時点で，

深度クローラは処理をやめる．このようにして，深度クローラは特定のサイト内を巡回して，新規のペー ジを収集していく．





















 

図5.4 深度クローラによるクロールの例．

5.2.2.4 RSS_クローラ

Webの情報を分析するとき，様々なトピックについての多様な人の意見が書かれているブログは絶好 の分析対象である．RSSクローラはブログの新規記事の情報が配信されるRSS (RDF Site Summary) フィードにアクセスして，新しい未収集のブログ記事がないかを確認し，あればそれをクロールする．

図 5.5はRSSクローラの構成と処理の概要を示している．RSSクローラはRSSフィードを収集する フィードクローラと，RSSフィードの情報を元に収集対象となるブログの記事（エントリ）のリストを 出力するエントリクローラとで構成される．フィードクローラの役割は，定期的にPingサーバへアクセ スすることにより，RSSフィードを収集することである．フィードクローラはまずPingサーバで提供 されるブログの更新情報を取得する（図 5.5(1)）．Pingサーバとはブログから更新情報を受け付け，複 数のブログの更新情報を管理し，第三者にブログの更新情報を提供する公開のサーバである．続いて，

フィードクローラはpingサーバから得られた更新情報からRSSフィードの情報を抽出し，抽出された RSSフィードをフィードDBに登録する（図5.5(2)）．フィードDBはフィードクローラが収集したRSS フィードの情報を管理するためのデータベースである．

このようして蓄積されたRSSフィードの情報を使って，実際に収集すべきブログエントリのリスト を生成するのがエントリクローラである．エントリクローラはまずフィードDB からRSSフィードの URLを取得する（図 5.5(3)）．次に，そのURLにアクセスし，RSSフィードを取得する（図 5.5(4)）．

RSSフィードはRDF やATOMなどのXMLに準拠した形式で記述されており，そのブログで最近公 開されたエントリのタイトル，公開日時，概要，URLなどの情報が掲載されている．エントリクロー ラはRSS フィードからエントリの URLを抽出し，URL DB に問い合わせて収集済みかどうかを確 認する（図 5.5(5)）．最後に，未収集のエントリについて収集対象としてリクエストリストを生成する

（図 5.5(6)）．エントリクローラがリクエストリストを生成した後は，図5.3のクローラの基本処理に沿っ

て，収集，ページ解析，DB更新が実行される（図5.5(7)）．