情報集約

(2007/05/08)

クロール周期の決定問題

クローラは収集したWebページなどを自身のデータベースなどに保存(キャッシュ)するわけですが、 Webページであれば更新されたり、サイトが引っ越して無くなる可能性があります。したがって、クローラはできるだけ頻繁にWebサイトを訪問し、キャッシュ・データを最新に維持したいと考えます。

しかし、クローラには頻繁に訪問できない理由があります。例えば、a) 頻繁な訪問によってネットワークや相手方Webサーバーの処理能力を逼迫する可能性がある、 b) 1箇所に何回も訪問していては訪問先全てをまわることができない、 c) クローラをホストするサーバーの処理能力が不足、などです。

こうした点を考慮すると、クローラはそのページが更新された時にちょうど訪問できればいいのですが、そんなに都合よくできるわけでもありません。しかしながら、この問題では多くの論文が発表されており、開発者はその知識を利用することができます (参考：山名早人："WWWサーチエンジンの最新技術"、人間主体の知的情報技術に関する調査研究IV、日本情報処理開発協会先端情報技術研究所、(2001))。

例えば、チェックしたページの更新有無によって次回クロール間隔を調整する方法は、比較的簡単に実装できると思われます (参考：Edwards K., McCurley K., Tomlin J.: "An Adaptive Model for Optimizing Performance of an Incremental Web Crawler",10th International W3 Conference,ACM,(2001))。この方法では、例えば既定では1ヶ月周期でクロールを行い、更新があった場合はチェック周期を半分にするといった調整を行います。結果として、頻繁に更新されるページは頻繁にクロールを行い、あまり更新されないページはそれなりにクロールするということになりますので、全体でのクロール回数や時間を最適化することができます。
ページ内のリンク探索とクロールを幅優先探索にする、というのも有効なようです (参考：Najork M., Wiener J.: "Breadth-first search crawling yields high-quality pages",10th International W3 Conference,ACM,(2001))。この方法では、Webサーバーの負荷分散が可能なほか、幅広いトピックが収集できるため、クロールの初期段階で重要なページを網羅することができるとされています。
クロール間隔を短くしすぎて相手Webサーバーがダウンしては何にもなりませんが、見かけは異なるホスト名でも実はバーチャルホストで同じ機器を利用している、というのはありそうな状況です。ブログ検索のような鮮度最優先のクローリングにおいても、そのような配慮をすべきという指摘がされています (参考：杉崎正之："goo Blog - Blog Search Technology"、gooオープンカンファレンスVol.2,(2006))

学術論文の多様なアイデアに触れると、実装レベルではおそらく多くの工夫の余地があるのだと思わされますが、その一方で、Googleに目を向けてみると、 Google主任科学者クリシュナ・バラト氏に対するインタビュー「ついに明かされるGoogle Newsの秘密」において、下記のように述べられています。

Google Newsが始まったときには、コンテンツをリアルタイムで索引するインフラストラクチャーができあがっていました。
それ以前の検索エンジンは、クローラーと呼ばれるロボットが、ときどきインターネットのいろいろなウェブページを巡回して、新しい情報を索引化（インデックス化）するといった仕組みで動いていました。

前後を読むと、クローリングに代わる技術革新によって、リアルタイムなインデキシングが可能になったように読み取れます。その技術の内容が気にかかりますが、神崎洋治ほか：「体系的に学ぶ検索エンジンのしくみ」,日経BPソフトプレス,(2004) によれば、巡回間隔を分単位に調整したクローラであると指摘されています。いずれにしても確実なのは、情報集約の問題が分刻みのインデキシングに到達しているという点でしょうか。

前：Webクローラとは何か | 次：クローラが招く問題

【関連ページ】