副テーマ中間報告 Development of a Scale Web Crawler By hajime TAKANO and Nobuya KUBO Trawling the Web for emerging cyber-communities Ravi Kumar, Prabhakar Rabhavan,

Presentation on theme: "副テーマ中間報告 Development of a Scale Web Crawler By hajime TAKANO and Nobuya KUBO Trawling the Web for emerging cyber-communities Ravi Kumar, Prabhakar Rabhavan,"— Presentation transcript:

1 副テーマ中間報告 Development of a Scale Web Crawler By hajime TAKANO and Nobuya KUBO Trawling the Web for emerging cyber-communities Ravi Kumar, Prabhakar Rabhavan, Sridhar　Ragopalan, Andrew Tomkins Reported by Kan Matsuda

2 Development of a Scale Web Crawler
NECの検索サービスNETPLAZAで用いられている検索サービスのweｂロボット“Nexplorer”の製作、実験について 実際に検索サービスに利用し検証 2000年11月9日 副テーマ中間報告

3 INTRODUCTION 検索サービスの主な機能は次の三つから成る． １.WWWのページを集める．
２.データベース内の集めたページを蓄え，管理する． ３.ユーザーが要求するページを探してくる． Web crawler:WWWのページを集めてくるエージェントシステム Webページは大量→素早い収集・最適化可能な基本構造が必要 Nexplorer:これらの要求を満たすWeb crawler 2000年11月9日 副テーマ中間報告

4 REQUIREMENTS FOR WEB CRAWLER
1ホスト100枚とすると 約4億3千万の ホスト 約430億のWebページ JPドメイン 約2億枚 Web crawlerの基本的な機能 HTMLからURLを見つける→それらのURLへ行ってドキュメントを得る Web　crawlerの設計 ハードウェア：複数のCPUを用いる ソフトウェア：並列処理ができる構成にする Web crawler:検索サービスのためにページを集めてくる． Web crawlerの基本的な機能 l          HTMLからURLを見つける→それらのURLへ行ってドキュメントを得る，を繰り返す→時間がかかる l          1日に1億枚のページを集めてきても全て集めるには1ヶ月以上かかる Web　crawlerの設計 l          ハードウェア：複数のCPUを用いる l          ソフトウェア：並列処理ができる構成にする l          その他：サーバにかかる負荷を軽減、不完全な応答が帰ってくること、ドキュメントそのものが不完全であることを考慮 l          情報は新しいほうが良いため更新する必要がある Web　crawlerに求められるもののまとめ l          出来るだけ早くWWWページを集められる l          HTTPやHTMLの進化に対応でき、かつ不完全なドキュメントに対しロバストである l          巡回の戦略は構成、制御可能 l          サービスの要求に十分な効率を供給できる調整が出来る 2000年11月9日 副テーマ中間報告

5 Functional Requirements
WWWページを出来るだけ早く集める 重要なサイトに優位性を加える 重要でないサイトの優位性を下げる コンテンツの種類によりページをフィルタリングする 巡回するサイトを選ぶ 予約語を含むページを除去する 深いディレクトリまたは特殊なものは無視する 2.2　Functional　Requirements WWWページを集める基本的なアルゴリズム 1.          URLデータベースにあるページのURLを得る 2.          URLにあるHTTPのWebサーバにアクセスしてURLにあうドキュメントを集める 3.          アクセス状態をURLデータベースにURLの属性としてセットする 4.          ダウンロードしたドキュメントにHTTPのURLがあったなら抽出する 5.          抽出したURLをデータベースに追加する 6.          1から5のステップを繰り返す Web　Crawが考慮すべき構成 l          URLデータベースはURLを蓄える l          データベースを管理するシステム l          Webサーバと対話する方法 l          HTMLを分析してURLを抽出する方法 サービスの観点からWeb　Crawが考慮すべき構成 l          WWWページを出来るだけ早く集める l          重要なサイトに優位性を加える l          重要でないサイトの優位性を下げる l          コンテンツの種類によりページをフィルタリングする l          巡回するサイトを選ぶ l          予約語を含むページを除去する l          深いディレクトリまたは特殊なものは無視する 2000年11月9日 副テーマ中間報告

6 BULDING A SERCH SERVICE
NexplorerをNETPLAZAで使用 CGIでキーワードを入力する JPドメインからWWWのページを集めてくる サーバを増やせば効率が良くなる ｇｏｏ等に負けないスピードを実現 2000年11月9日 副テーマ中間報告

7 CONCLUSION Nexplorerを作成 NETPLAZAで検索サービスとして利用し、検索サービスに十分な速さを実現している
より小さな規模へ適用し、スケーラビリティを確かめたい より戦略的なクルーリングへの機能拡張 2000年11月9日 副テーマ中間報告

8 Trawling the Web for emerging cyber-communities
Ravi Kumar, Prabhakar Rabhavan, Sridhar Ragopalan, Andrew Tomkins

9 Overvew Web上に数千の有名ではっきり定義されたコミュニティが存在 あいまいに定義されたコミュニティをトローリングにより抽出
抽出する理由 ユーザに良い情報を供給するため Webの発達を社科学的な観点から研究可能 ターゲットを絞った広告を出すことができる。 2000年11月9日 副テーマ中間報告

10 Strongly-connected bipartite subgraphs and cores
IBMとコンパックは相互リンクを張っていない 他のページでこの両方にリンクを張っているページがある 確かな価値判断ではないが、リンクの合計はページのクォリティを示す 関係の深いページどうしてはcoreを形成 2000年11月9日 副テーマ中間報告

11 Strongly-connected bipartite subgraphs and cores
F C core 仮説：ｗｅｂ上のランダムで十分大きくて濃度の濃いサブグラフはコアが確実にある 2000年11月9日 副テーマ中間報告

12 Data source and resource
データは1年半以上前の若干古いもの HTMLデータのみ1テラバイト分 約2億ページ分のデータ(やや少ない） PⅡ300MHz、Linuxで2週間未満の実験 2000年11月9日 副テーマ中間報告

13 Trawling system ノードに入ってくる枝の数iと、出て行くノードの数jからcoreかどうかを判断
Yahooなどのサイトは排除する (2,0) (2,1) (3,3) (1,1) i:入ってくるの数 j:出て行く数 2000年11月9日 副テーマ中間報告

14 Finixhing it off 約13万5千のcoreが発見される （３．３）の場合で約7万5千のｃｏｒｅが存在 2000年11月9日
副テーマ中間報告

15 Evaluation of communities
得られたcoreの中から無作為に400((3.3)、(3.5))のcoreを選ぶ 現在のweb上で同じcoreが存在するかを調査 400中130(約35%)のcoreが現存 2000年11月9日 副テーマ中間報告