インクリメンタルPageRankによる重要Webページの効率的な収集戦略東京大学山田雅信田浦健次朗近山隆背景  インターネットの爆発的な普及と情報の氾濫   サーチエンジンによる情報検索の普及サーチエンジンのお仕事 1. 2. 3. 4. クローラによるWebページの自動収集高速検索のための索引付け利便性向上のための検索結果のランク付けユーザインターフェースの提供 Overview   クローラにおける問題点問題解決のための先行研究とその手法   更なる改善を目指して・・・    PageRankクローラ PageRankクローラの考察とインクリメンタルPageRankクローラの提案実装と実験まとめ従来の多くのクローラに見られる問題点  Webページの重要度に基づくランク付けアルゴリズムの研究が盛んに行われている - 近年のサーチエンジンにおける検索精度の向上という事実  一方、クローラによるWebページの収集段階ではそのようなことはあまり考慮されていない  どのWebページも等しく扱い、等しく収集 e.g. 幅優先探索問題点により生じる不利益  クローラを取り巻く環境  時間的制限   物理的制限    定められた収集期間（約一ヶ月）ネットワークディスク全Webページの 30%程度のカバー率それらを浪費しつつ   一生懸命ゴミ集め - せっかく収集しても検索に利用される可能性が低いページが存在一方で重要なWebページの見落としも・・・ - 収集されないため検索対象にすらならない。誰にも気づいてもらえないクローラの収集戦略が重要 PageRankを利用した収集戦略  Efficient Crawling Through URL Ordering [J.Cho et al. 1998]  収集段階でWebページの重要度を計算、重要度の高いものから優先的に収集   重要度の計算にPageRankを利用実験内容： - それらを従来手法と比較、評価収集における精度を重視 PageRank  大規模リンク構造の利用    リンク = 重みのある支持投票投票結果の集計 = PageRank計算ブラウジングモデルの導入  ユーザがWebページ閲覧の際の行動パターンを数値化 - 多くの場合はリンクを辿ってページを閲覧 - 時にはそれ以外の方法で閲覧 PageRank ≒ Webにおける客観的人気度 e.g. google 収集手法(1) - Webページの収集優先度 step0 現段階で計算は完了しているとする：収集済み：未収集 ID-List step1 その計算結果に基づき収集優先度を決定 Priority-List step2 優先度の高いものから順に収集する収集手法(2) - Webページの収集：収集済み：未収集 ID-List 追加 step4 リンク構造を拡張 Priority-List 収集 step2 step3 収集したページからリンクを抽出するそのページが未知のものだったら新たに ID-Listに追加する収集手法(3) - PageRankにおける収集優先度の再計算：再計算中 ID-List step5 PageRankを再計算：収集済み：未収集：たった今収集 step6 ID-List内の全ての要素に対して計算を施行、それを必要に応じ複数回施行 step4 新たにページを収集したことによりリンク構造が拡張される考察 - PageRank収集戦略の利点と問題点  利点   幅優先探索やBackLink Countといった古典的手法に比べ、重要なWebページを優先的に収集することができる問題点  収集優先度計算のためのオーバヘッドが極めて大きい - PageRank計算はインクリメンタルなデータに向かない⇒実用的でないより低コストの計算方式が必要インクリメンタルPageRankへの導入  収集過程におけるリンク構造の拡張の大部分は、すでに保持しているリンク構造に比してごく小規模なもの e.g. １億ページからなるリンク構造に新たに１０００ページが追加された   リンク構造拡張にともなうPageRankの変化は全体からみれば微々たるもの（それにも関わらず）全てのページで再計算を行うのは、あまりにも非効率 PageRank収集戦略の利点を保ったまま計算コストを削減したいインクリメンタルPageRankを提案インクリメンタルPageRankのポリシー  ポリシー  リンク構造拡張にともなうPageRankの変化が比較的大きい部分のみ再計算を施行 - 当然そのことにより収集順序に誤差が生じるが、そのデメリットよりも計算コストの削減によるメリットのほうが大きい場合が多い  重要なページを“First”に収集するのではなく“Fast”に収集 - 収集順序の誤差により収集が１０分遅れたなどというのはあまり問題とはならない。 - 一番恐ろしいのは重要なページが収集されずに収集期間を終えることインクリメンタルPageRank における収集優先度の再計算：再計算中 ID-List step6 拡張された周辺のみ PageRankを再計算：収集済み：未収集：たった今収集 step5 リンク構造を拡張する際にはどのように拡張されたかをチェックする step4 新たにページを収集したことによりリンク構造が拡張される実験 - 擬似クローリング    あらかじめ収集しておいたデータを利用リンクをもつページをランダムに選び出し、それをクローリングの起点として登録各収集戦略によりクローリング - Priority-Listのソートは5000ページ毎 - Priority-Listが空になるか、あらかじめ指定したページ数を収集したら終了 - クローリングのログと結果を出力収集戦略   PageRank (PR) Incremental PageRank (IPR) - Overall Sort (OS) - Partial Sort (PS) -  Value Ratio (VR) Link Depth (LD) Page Number (PN) Back Link Count (BLC) - Overall Sort (OS) - Partial Sort (PS)  Breadth First Search (BFS) 収集優先度の計算速度比較 1800000 1600000 処理時間(ms) 1400000 1200000 BFS 1000000 BLC_OS 800000 IPR_OS 600000 PR_5 400000 200000 0 0 100000 200000 300000 収集ページ数 400000 500000 PageRankクローラに比べ圧倒的に低コスト! ページ収集におけるアイドル時間も有効利用!! インクリメンタルPageRankにおけるもうひとつの選択 - Partial Sort  Overall Sort - ある程度ページを収集した段階でPriority-Listをソートする - Priority-Listが膨大だとソートに時間がかかる  Partial Sort - インクリメンタルPageRankやBack Link Countにおいては新たにページを収集(リンク構造を拡張)したことにより収集優先度が上がるページが特定できるそのようなページのみPriority-Listをソートする - Overall Sortに比べPriority-Listのサイズによる影響が小さいソート手法の速度比較 900000 800000 処理時間(ms) 700000 600000 500000 IPR_OS IPR_PS 400000 300000 200000 100000 0 1 10 100 1000 10000 収集ページ数 100000 1000000 Partial Sortは頻繁にPriority-Listが更新されるとき性能が悪化ハイブリッド型の検討重要ページの収集率 25 上位10%の収集率(%) 20 15 BFS BLC_OS IPR_PS 10 5 0 0 100000 200000 300000 収集ページ数 400000 500000 インクリメンタルPageRankが圧倒的に優れている Overall SortとPartial SortではPartial Sortの方が若干優れている精度とコストのトレードオフ - 計算の打ち切り  Value Ratio (VR) - 新たにforwardするPageRankとforwardされる側のページのPageRankの比がある閾値以下  Link Depth (LD) - 起点からのリンクの深さがある閾値以上  Page Number (PN) - 更新されたページ数がある閾値以上になったら計算を打ち切る各計算打ち切り手法の精度比較 25 上位10%の収集率(%) 20 IPR_PS(LD1) IPR_PS_LD3 IPR_PS_LD5 IPR_PS_PN10 IPR_PS_PN100 IPR_PS_PN1000 IPR_PS_VR1 IPR_PS_VR001 15 10 5 0 0 100000 200000 300000 収集ページ数 400000 500000 収集段階によっては精度に約1～2% 程度の違いが見られるまとめと今後の課題  まとめ    インクリメンタルPageRankは幅優先探索よりも賢く、PageRankよりも高速な収集戦略現実のように全Webページのうち数十パーセントしかクローリングできないよな状況で特に有効課題   更なる効率化実際のWWW空間での実験と実用化