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