Download presentation
Presentation is loading. Please wait.
1
大学院情報理工学研究科 冬学期講義 ウェブ工学
大学院情報理工学研究科 冬学期講義 ウェブ工学 2007年10月1日 生産技術研究所 豊田正史
2
講義の進め方 11回の講義を予定 評価はレポート 2回くらい？ 出席は特に取らない 講義中の発言・質問は考慮するかも
3
研究対象としてのウェブ 膨大な文書集合 膨大なグラフ構造 動的 サービス提供の場
200億を超えるテキスト・画像・動画(Yahoo!発表2005/8) 自然言語処理、情報検索、情報抽出、テキストマイニング 膨大なグラフ構造 文書＝ノード、リンク＝エッジの膨大かつ疎な有向グラフ グラフ理論、複雑ネットワーク理論、情報検索への応用（PageRank, HITS) 動的 持続的な成長(サーバ数は2000年から年平均36％増加 米Netcraft社) 無数の著者が日々文書を生成する一方、消滅する文書も多い。 時系列解析(成長率、内容の変化、構造の変化)、社会学 サービス提供の場 広告、通信販売、メール、ブログ、写真共有、企業間取引 XML、Webサービス、セキュリティ、経済学
4
検索エンジンのサイズ 2004年 GG: 8.1B, 2005年 Y!: 20B
5
ウェブの継続的な成長傾向 米Netcraft社の調査
6
人間が入力できるテキスト情報の量 WWW2007 Keynote by Prabhakar Raghavan (Yahoo
人間が入力できるテキスト情報の量 WWW2007 Keynote by Prabhakar Raghavan (Yahoo! Research) Bytes/minの間違い？
7
今この辺？
8
WWW2008 Refereed Paper Tracks
Browsers and User Interfaces Data Mining (Highly competitive) Industrial Practice and Experience Internet Monetization (New!) Mobility Performance and Scalability Rich Media Search (Highly competitive) Security and Privacy Semantic / Data Web Social Networks and Web 2.0 (New!) Technology for Developing Regions Web Engineering WWW in China XML and Web Data
9
講義の内容 検索エンジンの仕組みと技術 グラフ・ネットワーク理論とウェブ 最新のトピック紹介 検索エンジンの構成法
情報検索 (Information Retrieval) リンク解析 (PageRank, HITS) グラフ・ネットワーク理論とウェブ ウェブグラフの構造と特徴 最新のトピック紹介
10
Why writing your own search engine is hard Anna Patterson (ACM QUEUE 2004)
Internet Archiveで30B文書を検索するサーチエンジンを書いた人(1998) その後、Googleへ 現在GoogleからスピンアウトしCuillという検索エンジンを開発中 数人のチームがガレージで検索エンジンを作ろうとするとき何を考えなくてはいけないか
11
Super short overview of SE
Crawlerがページを集める 大量のディスクが要る インデックスを作成する どのページがどの語を持っているか 普通Crawlerがページを貯めたディスクでローカルに行われる インデックスをまとめる たいてい1台でまかなえないほど大きくなるので複数のマシンに分散する ランタイムシステムを作る ユーザからの質問を受け付け 検索結果をインデックスを持つマシンから得る 質問に応じて検索結果をre-rankingする 素早く応答しなくてはならない
12
リソースに関する注意 Bandwidth CPU Disk Storing Files Networking
ディスクは安い。高くつくのはネットワーク帯域 CPU Crawlerは遅いCPUで良く、インデックス、サービスに速いCPUを使う クロックよりキャッシュサイズが重要 Disk SCSIはより速いがIDEはより大きく安い。IDEがベター 今ならSAS,SATA IDEなら1台のマシンで1TBは余裕 SCSIの速さはユーザに分かるほどではない。並列化のほうが効果的 耐故障性はSCSIのほうが上。 Storing Files 大きなファイルに多数の文書、ＵＲＬを詰め込むのが良い。ディスクのシークを大幅に減らせる。 百万単位の文書を処理するのに１０KB程度の文書を読むたびシークするのは大変 Networking NFSは使うな。シビアな利用には対応していない
13
ソフトウェア Crawler Indexing Ranking Serving 最初はURLのリストをGETするだけのシンプルなもので
取ったページのアウトリンクを抽出して重複を除き再取得を繰り返す。内容の重複は取った後で考える 動的に重複を除くのは非常に難しい。 Indexing 最初は語を索引するだけのシンプルなものでよい あまりややこしいことはせずランキングを頑張る Ranking 最初からPageRankなど使わず、HTMLソースの特徴を使う PageRankには余計なコストがかかる Serving インデックスから結果を得て、結果を適合度でソートし、綺麗な結果ページとして出力する。簡単そうに見えて結構大変 2語以上のクエリではリストの積を高速に取る必要がある。リストを事前にソート。 リストを得たらそれをランキングする。事前にランキングしておいてそれを用いてソートするのが一番早いが、結果が一般的なものになる。クエリに応じてランキングを変えるにはインデックスに少しデータを追加する必要がある
14
次回以降の予定 10月8日は休日 10月15日 第2回 10月22日 休講
10月15日 第2回 The Anatomy of a Search Engineを読む予定 Sergey Brin, Lawrence Page Googleの元論文 10月22日 休講
Similar presentations
