Fetterly, Dennis*., Manasse, Mark**., Najork, Marc**. Wiener, Janet*. "A Large-Scale Study of the Evolution of Web Pages", Proceedings of the 12th International Conference on World Wide Web. p.669-678(2003)
* Hewlett Packard Labs, Palo Alto, CA. ** Microsoft Research, Mountain View, CA
※図表、注・引用文献は原文献をご参照下さい。
1. はじめに
ウェブはどのくらいの速さで変化しているのか、コンテンツは継続的にアップデートされているのか否か、ページの変化はページの属性と関連性があるのかといった様々な疑問は、ウェブから情報を探そうとする人々にとって興味深い問題であるものの、一部の例外を除いて実証的な研究は少ない。
本論文では、11週間に亘って、150,836,209のウェブページをクローリングし、ページのチェックサムと出現する語彙の特徴ベクトルを保存した。
そして、各々のページの変化の度合いを分析して、どのような要素が変化の度合いに強く関連しているのかを調査するとともに、クローリングやデータの抽出方法について詳述した。
2. 関連研究
本論文はChoとGarcia-Molina[5]による研究を拡張したものである。Choらは270のポピュラーなウェブサーバから(1サーバあたり3,000ページを超えないように)4ヶ月間毎日720,000ページをダウンロードし、各ページのHTMLタグを含むコンテンツのMD5チェックサムを保存した。
これによって、どの程度の変化であるかは不明であるものの、ページが変化したか否かを確認することができるようになる。
調査の結果、全てのウェブページの40%は1週間以内に変化すること、50日間に全体の50%が変化すること、comドメインの25%は一日で変化すること、comドメインのページが半分変化するための期間は11日間であるが、govドメインの場合は4ヶ月間を要すること等を明らかにした。
本研究は幾つかの点で先行研究とは異なっている。
第一に、Choらの研究の約200倍のサンプルを用い、ウェブのより大きい部分をカバーしている。
第二に、これまでの研究で用いられたものよりも、きめの細かい手法でページの異同を判定している。
第三に、他の研究に内在するバイアスの問題を除去するために、幅優先探索によるクローリングによってページを選択している。
第四に、我々は全てのページの0.1%の全文を保存している。
3. 実験手続き
3.1 データ収集
まず、2002年11月26日から12月5日にかけてクローリングを行い(crawling 1)、1億5千万のHTMLファイルと6千万のHTML以外のファイルをダウンロードした。
その後、10週間に亘って、さらに10回ずつ、これら1億5千万のHTMLファイルのダウンロードを試みた。
図1はダウンロードの成功回数の分布を示している(→図1)。
11回全てダウンロードできたのは全体の49.2%のページ群であり、33.6%は10回成功、残りの17.2%は9回以下の成功であった。
クローリングはYahoo!を種として、Mercator[8]を用いて行った(https, ftp, gopher等http以外は無視した)。
残りの10回のクローリングは2002年12月5日〜2003年2月12日まで継続的に行った。
次に、統語論的特性に基づいた文献の類似性を測るBroderら[4]の手法を改良して、文献の特徴ベクトルを算出した。
まず、HTMLタグを除去し、連続する五つの語彙をshingleと呼び、各shingleのチェックサム(pre-imageと呼ぶ)を算出した。最初にダウンロードしたページから84のpre-imageを無作為に抽出し、それらが修正されたページに出現するか否かを確認することによって、ページの類似性の尺度(特徴ベクトル)とした。
また、クローリングの際、生データのチェックサム、HTTPステータスコード、document length、タグを除く文字数、URL等のログを取り、ハッシュ関数によって無作為に抽出された全体の0.1%のページについては全文を保存した。
3.2 データの抽出
ログは全部で1,200GBとなり、そのうち、サンプリングされたページは59GBであった。
この段階で、生データのチェックサムやpre-imageそのものは保存せず、どの程度一致しているかという情報のみを抽出し、222GBまでサイズを減らした。
3.3 データの発掘
Javaで分析装置を実装してログを解析し、以下の結果を導き出した。
4. 結果
図2はダウンロードした全1,482,416,213ページのdocument length(HTMLタグを含む)のヒストグラムである(→図2)。
x軸の数値nはファイルのサイズが2nバイト以下であることを意味する。
これは平均14、標準偏差1の分布であり、全体の66.3%のHTMLファイルが4KB〜32KBの大きさであった。
全体の52.5%がcomドメインであり、orgドメインとgovドメインはそれぞれ8.0%と1.1%であった。
eduドメインのページはやや小さく、edu全体の64.9%が2KB〜16KBの範囲にあった。
図3は、HTMLタグを除去したファイルサイズのヒストグラムである(→図3)。
図4は、11回のクローリングにおいて、全てのページについて、どのようなHTTPステータスコードが返されたのかの分布を示している(→図4)。
このうち、RobotExclはcrawling 1の段階ではアクセス可能であったが、その後、robots.txtでロボットを排除するようになったものである。
図5は、11回のクローリングにおいて、ダウンロードを試みたもののうち、実際にダウンロードすることのできたページの比率の推移である(→図5)。
図6は11回のクローリングにおいて、ダウンロードが成功したページの比率をドメインごとに示したものである(→図6)。
y軸の最低値が75%となっているのは、11週間経ってもアクセス可能であるページの比率が最も低いものでも75%より高いことを示している。
※訳者注:11回連続でダウンロードできたか否かではなく、11回目のクローリングでダウンロードできるかどうかを確認している点が図1の視点と異なっている。
ドメインごとの比較では、cnドメイン(中国)のページが比較的消去されるのが早いことが分かる。
図7は84のpre-imageとファイルのチェックサムの一致度の累積分布を示したものである(→図7)。
全体の65.2%は全く変化がなく、9.2%はファイルのチェックサムのみが変化している(これは予め除去されたHTMLタグに変化があったものと考えられる)。
図7中の(累積ではない)度数分布の部分のみを拡大表示したものが図8である(→図8)。
ここから、ほとんどの変化は2%未満であることが分かる。
トップレベルドメインとファイルの変化の度合いとの関係を示したものが図10である(→図10)。
Choら[5]の調査結果とは異なり、comドメインのページはgovドメインやeduドメインと比較してより変化していることが明らかになった。
また、deドメインのページは他のドメインと比較して頻繁に変化している。
図13はファイルのサイズとファイルの変化の度合いとの関係を示したものである(→図13)。
その結果、よりサイズの大きいページ(32KB以上)のページの方がより変化していることが分かる。
図14は文字数とファイルの変化の度合いとの関係を示したものであり(→図14)、図13と同様の傾向が見られる。
図16はドメインごとに文字数とファイルの変化の度合いとを示したモノである(→図16)。
comドメインやnetドメインはファイルの大きさと変化の度合いの関係がより強く見出される。
5. 結論
本論文では一定期間におけるウェブページの変化の度合いを測定するための大規模な実験について記述した。
その結果、ほとんどのページの変化はHTMLのみか、ほんの僅かなものに過ぎないことや、トップレベルドメインやファイルのサイズによって変化の早さが異なることが明らかになった。
また、過去の変化の早さによって、将来の変化の早さを予測することができることも示した。
|