スライド 1

大学院情報理工学研究科
冬学期講義
ウェブ工学
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
– 大きなファイルに多数の文書、URLを詰め込むのが良い。ディスクのシークを大
幅に減らせる。
– 百万単位の文書を処理するのに10KB程度の文書を読むたびシークするのは大
変
• 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日
休講