情報システム第二 (3) 検索エンジンはどう動くのか?

情報知識ネットワーク特論 (兼ERATOセミナー):
検索サービスを支える技術
2013-12-03
日本電信電話株式会社
数原 良彦
1
自己紹介
• 数原 良彦 (すはら よしひこ)
– 所属: 日本電信電話(株) NTTサービスエボリューション研究所
• サービス／製品化に向けた研究開発
• 基礎研究 ⇔ 応用研究 ⇔ サービス／製品化
• 業務内容 (過去～現在)
– 主に情報検索に関わる研究開発
• 検索エンジンの高性能化
• 機械学習を用いた検索ランキングの高精度化
– ランキングモデルの構築
– 自動スパム判別
• 地理日時検索サービスの開発・運用
• テキストからの地域イベント情報抽出
• 移動履歴からのユーザ状態推定
2
本日の講義では
• 以下のことを理解できるよう発表に努めます
– (1) NTT研究所と地理情報検索に関する取り組み
– (2) 転置インデクスを用いた全文検索エンジンの仕組み
– (3) 研究開発の現場で使われている技術や苦労するポイント
3
本日 (暗黙的に) お伝えしたいこと
• まずアルゴリズムを考える．それを計算機で動かすことを考える
• その間にいろいろノウハウが必要であること
数理モデル・
アルゴリズム
大学で習う知識
ノウハウ
現場で必要なノウハウ
※必ずしも大学で学ばないわけではない
e.g., 数値計算，コンパイラ etc.
計算機
アプリケーション・
サービス
4
本講義の流れ
• 発表内容
–
–
–
–
NTT研究所における地理情報検索の取り組み (10min.)
検索エンジンの概要と仕組み (40min.)
大規模検索を実現する工夫 (20min.)
質疑応答 (適宜)
• 事前知識を仮定していません
– わからないことがあれば適宜質問してください
5
NTT研究所における
地理情報検索の取り組み
6
地理情報検索の概要:
キーワードと地理範囲を入力とします
(1) キーワードによる全文検索
キーワードと地理範囲に
合致する文書を取得
見所
(2) 地理範囲による空間検索
7
発見探地図エリアダス
• 地理情報検索サービスのスマートフォン向け
アプリケーション
– 地理情報検索技術の公開実験
• 2011年12月～2013年9月
• かつて Google Play で公開
– 公式ページ http://areadas.jp/
8
エリアダスの紹介ムービー
• 動画 (約1分)
9
まとめ: エリアダスでできること
地理情報検索機能
キーワード分布図
キーワード推薦
検索キーワード、地理条件
での文書検索
地図上に検索キーワードに関
する情報量を分布図で表示
地図上に地理条件で
特徴的なキーワードを推薦
2013/12/5
10
まとめ: エリアダスでできること
地理情報検索機能
キーワード分布図
キーワード推薦
検索キーワード、地理条件
での文書検索
地図上に検索キーワードに関
する情報量を分布図で表示
地図上に地理条件で
特徴的なキーワードを推薦
本日はこの機能を実現する
検索エンジンを中心に紹介します
2013/12/5
11
地理情報検索の概要:
キーワードと地理範囲を入力とします
(1) キーワードによる全文検索
キーワードと地理範囲に
合致する文書を取得
見所
(2) 地理範囲による空間検索
12
地理情報検索の概要:
キーワードと地理範囲を入力とします
キーワードと地理範囲に
合致する文書を取得
(1) キーワードによる全文検索
見所
(2) 地理範囲による空間検索
ここから先は
「全文検索エンジン」
を中心にお話しします
空間検索も少し紹介
13
検索エンジンの仕組み
14
検索エンジンが活躍しているところ
• ウェブ検索
• ファイル検索
• メール検索など
15
検索エンジンは
計算機で動くプログラム
16
検索ロボ
• 検索エンジンのプログラムを擬人化
検索ロボ
17
検索ロボに聞く
「北大」を含む
文書は?
カチャカチャ
ユーザ
18
検索ロボの (一番大事な) 仕事
検索ロボは検索対象の文書群から
入力されたキーワードを含む文書を特定し，
ユーザに教える
キーワード
「北大」
検索対象の文書群
コレ
コレ
19
文書って何? 全文検索編
• 本やウェブページなどテキスト表現されるもの
北海道大学
=
文学部
文学部
教育学部
法学部
経済学部
理学部
医学部
歯学部
薬学部
工学部
農学部
獣医学部
水産学部
・・・
20
質問: あなたが検索ロボだったら?
• 課題
– 手元の本から
– 入力されたキーワードを含む箇所を報告する
• どうやって探す?
21
回答1
22
回答1: 1ページずつ眺める
• 一冊ずつ眺めて該当箇所を報告
– 該当箇所を漏れなく報告できる
23
回答1の問題点
• 本が増えると大変
– 本が10倍 ⇒ 10倍のコスト
大変!
24
回答2
25
回答2: 索引を利用する
• 本の索引を利用して検索
– どの文書のどの位置に出現するか
– 文書の量によらず，同じ速度で高速に探し出すこ
とが可能
索引帳
26
回答2: 索引を利用する
• 本の索引を利用して検索
– どの文書のどの位置に出現するか
– 文書の量によらず，同じ速度で高速に探し出すこ
とが可能
索引帳
ポイント
索引にないと調べられない ⇒ 索引をどうつくるか?
27
検索エンジンは
索引を使って検索する
28
検索ロボは合体ロボ
1号
検索対象の文書を集めるロボ
2号
索引を構築するロボ
3号
索引の検索を行うロボ
29
本日のメインは2号，3号
1号
検索対象の文書を集めるロボ
2号
索引を構築するロボ
3号
索引の検索を行うロボ
30
準備:
検索エンジンの索引構造
1号
検索対象の文書を集めるロボ
2号
索引を構築するロボ
3号
索引の検索を行うロボ
これの事前知識
31
検索エンジンの索引構造
• 転置インデクス (inverted index) と呼ばれる
データ構造を用いる
– 本の索引と基本的に同じ
辞書 (dictionary) /
語彙 (vocabulary)
転置リスト (inverted list)
見出し語
北大
(DocID; <position>, DocID; , …
講義
DocID; <position>,…
検索
DocID;
エンジン
DocID;
32
具体例
見出し語
北大
講義
検索
エンジン
1; <3, 8>, 2; <1>, …
1; <5>, …
1; <10>, …
1; <11>, …
33
見出し語の決め方
• 検索の観点から適切な単位で区切る必要あり
– 実はとても大切な問題
– 日本語の場合は「形態素解析」と呼ばれる言語処
理技術が利用されている
• 本講義では「適切な単位」で見出し語を切り出
すモジュールがあるという前提で話を進める
34
辞書に必要な情報
• 見出し語と，見出し語に対応する転置リストへのポインタを保持
– ポインタ =メモリ／ディスク上の番地番号
• 辞書の実装に用いられるデータ構造
– ハッシュテーブル
– トライ木
• パトリシアトライ，ダブル配列など
– 簡潔データ構造
• LOUDSなど
◆辞書の要件
見出し語
◆トライ木の例
転置リスト
t
h
r
o
k
北大
0x112233
講義
0x112245
i
e
検索
0x112252
e
e
DocID; <position>, DocID; , …
DocID; <position>,…
エンジン
0x112260
DocID;
DocID;
35
転置リストの実装例
• 使い方に応じて格納形式を選択
– DocIDのみ
– DocID + Position
見出し語
北大
Freq: DocID, DocID, …
講義
検索
エンジン
36
補足: Googleではどうやっているか?
• 位置情報のみの転置リストを利用 [Dean+ 09]
見出し語
北大
Freq: position, position, …
講義
検索
エンジン
• この場合「位置情報 ⇒ 文書ID」の変換が必要
– 例えば下図のような変換テーブルを二分探索
文書ID
開始位置
1
1
2
120
3
180
…
…
N
17280
37
[Dean+ 09] Jeffrey Dean, “Challenges in Building Large-Scale Information Retrieval Systems”, WSDM ‘09 Tutorial, 2009.
補足: 二分探索のチカラ
• 1億文書の探索コスト
15
10
5
0
log2(x)
20
25
– log2 (10^8) ≒ 25回
0e+00
2e+07
4e+07
6e+07
x
8e+07
1e+08
38
脱線: 人力二分探索
• 未知の言語の辞典
– 謎の単語 “Jingisukan” を調べる
– 辞典の中身はどうやらアルファベット順
– けれど単語に用いられるアルファベットの分布は未知
本を開くのはとても疲れるので
本を開く回数は最小にしたい
どうやって探す?
辞典
39
脱線: 最後の方
わざわざ二分探索するのもどかしい!
• CPUも似たような特性を持つ
– メモリのある部分を読み込んだ際に先読みしてキャッシュに格納
– さきほど読み込んだ部分の後ろを探していく場合には，キャッシュ
内を参照するため，メモリからデータを取得する必要がない 
– 二分探索の初期はキャッシュミスを引き起こす 
キャッシュ
CPU
まずここを探す
メモリ
40
索引の構築
1号
検索対象の文書を集めるロボ
2号
索引を構築するロボ
3号
索引の検索を行うロボ
41
索引の構築
• 入力文書を転置インデクスに変換する
2号
文書群
転置インデクス
42
索引構築の流れ
• 各文書について
– 1. 文書を見出し語列に変換 (トークン化)
– 2. 見出し語列の文書IDと出現位置を転置インデクスに追
加
• 全文書について上記処理を繰り返す
43
(文書ID: TF; 出現位置)
今日は北大
で講義
1. トークン化
DocID = 5
今日
は
北大
で
講義
(5: 1; 1)
(5: 1; 2)
(5: 1; 3)
(5: 1; 4)
(5: 1; 5)
2. 転置リストへの追加
見出し語
今日
+(5: 1; 1)
は
北大
で
講義
+(5: 1; 2)
+(5: 1; 3)
+(5: 1; 4)
+(5: 1; 5)
44
文書IDテーブルの作成
• 文書IDは追加された順番で文書に付与
– 同時に文書ID ⇒ 文書名も保持
– ウェブ検索の場合，文書ID ⇒ URLの対応表を保持
文書ID
URL
1
http://hoge.com/index.html
2
http://hoge.com/link.html
3
http://fuga.ne.jp/index.html
…
…
N
http://piyo.co.jp/inde.html
45
索引の検索
1号
検索対象の文書を集めるロボ
2号
索引を構築するロボ
3号
索引の検索を行うロボ
46
検索処理の概要
• 入力されたキーワードを含む文書を取得し，結
果を表示する
1. 入力クエリを含む文書を見つける
2. 検索結果のランキングを行う
3. 文書のスニペットを生成し，提示する
キーワード
3号
47
ロボをさらに分割
3-A号
文書をランキングするロボ
3号
索引の検索を行うロボ
入力されたキーワードを含む
文書を取得するロボ
3-B号
文書のスニペットを生成するロボ
3-C号
48
ロボをさらに分割
3-A号
文書をランキングするロボ
3号
索引の検索を行うロボ
入力されたキーワードを含む
文書を取得するロボ
3-B号
文書のスニペットを生成するロボ
3-C号
49
入力キーワードを含む文書の取得
キーワード
3-A号
文書IDの集合
50
単純な検索の実現方法
• 辞書から見出し語を見つける
• 該当する見出し語の転置リストを取得する
– 転置リストに含まれる文書を結果として返す
「北大」で検索
見出し語
今日
は
北大
で
講義
51
例) 単純な検索
• 見出し語に対応する転置リストに含まれる文書
を返す
北大
1
結果： 1
2
2
4 11 31 45
4 11 31 45
52
AND検索の実現方法
• 転置リストの積集合を取得 (併合処理)
– (1) 線形併合
– (2) 二分探索に基づく併合
– (3) スキップリストを用いた併合処理
• 例)
– “北大 AND 講義” で検索
– 北大と講義の転置リストに含まれる文書を取得
見出し語
今日
は
北大
で
講義
53
(1) 線形併合を用いたAND検索
終了！
北大
1
2
4 11 31 45
講義
1
2
4
1
2
4
結果：
5
6 16 57
54
(2) 二分探索に基づく併合処理
• 2つの転置リストの差が大きい場合には二分
探索を用いると高速に処理が可能
11-302
講義
11 16
1
2
4
5
6 16 57 …
理屈上はそうだが，二分探索はキャッシュを有効に利用できないため，
教科書どおりの性能が出ない 
55
(3) スキップリストを用いた併合処理
• 転置リストの文書IDは昇順に並んでいるため，定数個飛ばしの文
書IDを格納したスキップリストを利用して線形併合を効率化
スキップリスト
北大
511
1
1
2
急行
・・・
4 511 531 545
急行と各停を
乗り継いで探索
スキップリスト
講義
1
1
2
4
各駅停車
・・・
5
57
・・・
5
6 16 57
・・・
転置リスト
多層スキップリストも利用できるが，実用上1-2段で十分
56
複数AND検索の併合順序
• どの順番に併合すれば効率がよいか?
– 例) “北大 AND 講義 AND 検索”
北大
1
2
4 11 31 45
講義
1
2
4
検索
2 31 54
5
6 16 57
回答例: 転置リストが短いもの同士から併合する
57
※見出し語を短い単位で区切ってしまうと併合が大量発生 
フレーズ検索
• 複合語クエリの検索 (連接処理)
– 内部で複数の見出し語に分割されるもの
– 例) “東京都” => “東京” “都”
• 基本的にAND検索と同様の処理
– 文書IDに関する併合処理
– 位置情報に関する併合処理
58
1. 複合語クエリを構成する見出し語の取得
東京都
形態素解析
東京
併合処理と
照合処理の違い
都
2. 転置リストの取得
東京
1
都
1
<3,65,69> 144 <1,5,6,8> 170
<6,7,9>
3. フレーズ処理
1 144 170
<2,5,8> 144
<2,56,80>
DocID:1
文書IDの併合
1 144
併合処理（文書ID）
<1,5,6,8>
+
+
<6,7,9>
1<>
<2,56,80>
=
3 144
DocID:144
<3,65,69>
=
1
3
<2,6,68,70>
文書144
の1番目
144<1,2>
照合処理（出現位置）
59
検索処理のまとめ
• 検索処理は
– 見出し語に対応する転置リストを取得し，
– (AND検索，フレーズ検索の場合には) 併合処理
を行って，対応する文書ID集合を取得する
• 高速化のポイント
(1) 見出し語に対応する転置リストの取得
(2) 複数の転置リストの併合処理
60
地理情報検索におけるランキング，スニペット生成については
次回 (12/10) に (一部) 紹介予定
3-A号
文書をランキングするロボ
3号
索引の検索を行うロボ
入力されたキーワードを含む
文書を取得するロボ
3-B号
文書のスニペットを生成するロボ
3-C号
61
番外編:
地理索引の構築と検索
62
地理条件による文書の取得 (1/2)
(1) キーワードによる全文検索
キーワードと地理範囲に
合致する文書を取得
見所
(2) 地理範囲による空間検索
63
地理条件による文書の取得 (2/2)
• 地理条件に該当する文書を取得するための索引は
どうすればよいのだろうか?
この範囲の情報を含む
文書を取得したい
64
文書から地理領域情報の抽出
※詳しくは来週 (12/10) に解説
• ブログ記事の文章中に含まれている地名表現から
地理領域情報を抽出
久しぶりの映画
2010/05/05
昨日はみなとみらいに行きま
した。
ワールドポーターズで映画を
観ました。
キーワード
ワールドポーターズ，映画
2013/12/5
地理情報
地名表現を地理領域情報に変換
座標：緯度：xxx，経度：yyy
領域： x1x1x1, y1y1y1, x2x2x2, y2y2y2
65
R-tree: 空間的なクエリを処理するためのデータ構造
• R-tree
– クエリが含まれる/重なりのあるエリアを検索する空間インデクスデータ構造
– B-tree の多次元版と考えるとイメージがつきやすい
横須賀市
神奈川県
×
久里浜
“空間インデクス” と呼ばれるものは内部では
R-tree を使うことが多い
e.g., MySQL, PostgreSQL (PostGIS) etc.
•
R-tree 改良のポイント (主にインデクス構築)
– オブジェクト挿入：どこに新しいオブジェクトを挿入するか
– ノード分割：どのように領域を分割するか
– e.g., R*-tree [Bekmann+ SIGMOD ‘90], Revised R*-tree [Beckmann+ SIGMOD ‘09] など
66
脱線
N. Beckmann: R-treeひとすじ20年!
67
大規模データを扱う工夫
68
大規模データを扱う工夫
• 一台のマシンには性能の限界
– 超大規模なウェブ文書は一台では扱いきれない
• 大規模データを扱う工夫
1. 索引を効率よく格納する
⇒ 転置リストの圧縮
2. 複数のマシンを利用する
⇒ インデクスの分散
69
転置リストの圧縮
70
転置リストの圧縮
• 転置インデクスの大部分を占める転置リスト
を圧縮する
– ただし，情報は全て正しく復元できる必要がある
できるだけ小さくしたい!
71
文書ID格納に必要な容量
• bit = 0/1を表現
• 2bit は0-3までの数字を表現可能
• N文書を表現するためにはlog2N bit必要
• 例)
– 200文書を格納している転置インデクスの文書IDには，
– log 2 200 = 8 bit 必要
– 8bit × 転置リストの総エントリ数 の容量が必要
72
転置リストを配列で実装する
• 配列は固定長
– 箱の大きさが1つでも違うとi番目の要素を取得できない
北大
1 2 4 11 31 45
10進表現 (イメージ図)
2
1
8bit
8bit
11
…
0000 0110
…
4
8bit
8bit
実際のメモリ上では
0000 0001
0000 0010
0000 0100
使わない先頭4bitを削れないか?
73
可変長バイト符号 (Variable-byte code)
• 可変長バイト列で表現
• 8 bit (= 1byte) を以下のように解釈
– 1 bit: 次の8bitが連続するかの判定フラグ
• 0=次の8bitに続く, 1=ここで終わる
– 7 bit: 数字本体を格納
• 8bitは見づらいので，4bitで解説
– 例） 0001 1001 => 1001(2) => 9(10)
文書IDのビット長を更に短くする
• 値の差分を取る
– 情報は変わらない
– (気持ち) どうせ前から読み込むし
北大
北大
1
2
4 11 31 45
1bit
2bit
2bit
1
1
2
1bit
1bit
2bit
4bit
5bit
6bit
7 20 14
3bit
5bit
5bit
75
クイズ：Variable-byte codes
• 8bitはタイヘンなので，4bitバージョン
– 例） 0001 1001 => 1001(2) => 9(10)
• 問題：以下のbit列からdocIDリストを求めなさい
1001 0001 1011 1011
• 解答
– gap = [1, 11, 3]
– docID = [1, 12, 15]
ガンマ符号 (γ codes)
• 差分を<length, offset>で表現
– lengthはunary codeで表す
• 5 => 111110
– offsetはbinary code
• 具体例で説明
ガンマ符号の例: 13
• エンコード
–
–
–
–
–
–
–
13(10) => 00001101(2)
00001101
00001101
1101 => 1101 (offset length = 3)
unary符号で3 は 1110
< 1110, 101>
1110101
• デコード
– 1110101
演習：ガンマ符号
• 13 = <1110,101>
• 9=?
• ? = <10,1>
• 解答
• 9 = <1110,001>
• 3 = <10,1>
• よって[3, 9, 13] => 10111100011110101
ガンマ符号の発展: デルタ符号 (δ code)
• ガンマ符号のlength部分をガンマ符号で圧縮
•
•
•
•
例）
9(10) = 1001(2)
1001 = <1(10), 001>
1(10) = <10, 1>
• ∴<1(10), 001> = <101, 001>
転置リスト圧縮のまとめ
• DocIDの差分を取って圧縮
– 位置情報も基本的に同じ
• 圧縮率 vs. デコード速度
– 検索エンジンはデコード速度を重視
• 実用的にはVariable-byte符号で十分
– GoogleはVariable-byte符号の改良版を利用 [Dean 09]
– デルタ符号，ガンマ符号は圧縮率は高いが，CPUに優しくない 
• スキップリストとの相性もよくない
81
インデクスの分散
82
索引の分散
• 今までは転置インデクスが一台に格納されている前提
だった
• ウェブ文書のような大規模データは一台に格納できないの
で転置インデクスの分散を行う
83
インデックスの分散方法
• 転置インデックスの分散方式
(1) 見出し語による分割
(2) 文書による分割
84
(1) 見出し語による分割
85
見出し語による分割
• 見出し語でインデックスを分割
– クエリ毎にノードを選択し，検索結果を取得
• 例）
– マシン1: A-Mから始まる単語に関する転置インデックス
– マシン2: N-Zから始まる見出し語に関する転置インデクス
マシン1 A-M
マシン2
N-Z
86
問題点1
• フレーズ検索やAND検索のコストが高い
– 複数のノード間で転置リストの併合をする必要
クエリBrutus
クエリCaesar
・・・
インデックスa
インデックスb
インデックスc
Brutus
1
2
4 11 31 45
Caesar
1
2
4
5
6 16 57
87
問題点2
• 分割の最適化が困難
– 単語の分布などによる事前の解析が困難
– クエリ分布や単語の共起に依存
・・・
A-
Bどっちがいい?
C-
・・・
A-AN
AO-AZ
B-C
88
(2) 文書による分割
89
文書による分割方法
• 文書単位で転置インデクスを分散
– 例えばURLのハッシュ値やホスト名などを用いる
goo.ne.jp
google.co.jp
・・・
hatena.ne.jp
yahoo.co.jp
90
検索結果の取得とランキング
• k件の検索結果を取得する場合
– 各ノードから上位k件を取得し，その中から上位k件
を取得
上位k件
上位k件
上位k件
上位k件
※ 中間管理職サーバを設けてピラミッド状の多段階文書分散インデクスを利用することもある 91
問題点
• 文書頻度 (DF) のような大域的な統計値を計算し
づらい
– 全てのインデックスに問い合わせる必要がある
Caesarを
む文書数？
2件
0件
5件
・・・
なんらかの方法でサボる
⇒ ウェブ検索エンジンの検索結果件数が正確でない理由
92
まとめ
93
検索エンジンの構成
94
検索対象の文書を集めるロボ
1号
索引を構築するロボ
2号
入力されたキーワードを含む
文書を取得するロボ
索引の検索を行うロボ
3-A号
3号
文書をランキングするロボ
3-B号
文書のスニペットを生成するロボ
95
3-C号
検索エンジンの最小構成
本日紹介した内容
96
検索対象の文書を集めるロボ
1号
索引を構築するロボ
2号
入力されたキーワードを含む
文書を取得するロボ
索引の検索を行うロボ
3-A号
3号
文書をランキングするロボ
3-B号
文書のスニペットを生成するロボ
97
3-C号
さいごに
98
(再掲) 本日 (暗黙的に) お伝えしたいこと
• まずアルゴリズムを考える．それを計算機で動かすことを考える
• その間にいろいろノウハウが必要であること
数理モデル・
アルゴリズム
大学で習う知識
ノウハウ
現場で必要なノウハウ
※必ずしも大学で学ばないわけではない
e.g., 数値計算，コンパイラ etc.
計算機
アプリケーション・
サービス
99
技術者の私から一言
本日の裏メッセージ
• (1) 本日の内容は，大学院で最先端の研究に触れているみなさん
からすれば，あまり新鮮味のない方法だったと思います
– はい，世の中は意外と当たり前の技術で動いています
– みなさんが今学んでいる技術は，将来の当たり前になるかもしれま
せん
• (2) 社会に出るとほとんどのことがらに解答はありません
– 状況に応じた回答を素早く出すことが求められます
• (3) どう動くのか? なぜそれがよいか? 代替案はないのか? というこ
とを常に考えましょう
– 他人に対して説得的な説明をできるようにする
– 知識そのものは役立たずとも，道具の仕組みとよさを理解する訓練
にはなります
100
文献紹介
101
文献紹介 (1/3)
• [1] 山田浩之, 検索エンジンはいかにして動くのか?, gihyo.jp
– http://gihyo.jp/dev/serial/01/search-engine
• [2] 森大二郎, “検索エンジンはなぜ見つけるのか”, 日経BP
社 (2011)．
[2]
102
文献紹介 (2/3)
•
[3] Christopher D. Manning, Prabhakar Raghavan, Hinrich Schuetze,
“Introduction to Information Retrieval”, Cambridge University Press (2008).
– Webで全ページ公開されている．情報検索全般的にバランスよく書かれている
– 日本語訳「情報検索の基礎」も2012年発刊
•
[4] Bruce Croft, Donald Metzler, Trevor Strohman, “Search Engines:
Information Retrieval in Practice”, Pearson Education (2009).
– 検索エンジン寄りの話．エンジニア向けに書かれている．一番簡単かも．
•
[5] Stefan Buttcher, Charles L. A. Clarke and Gordon V. Cormack, “Information
Retrieval”, The MIT Press, 2010.
– 検索エンジン実装寄りの話．結構マニアックな話題あり．
[3]
[4]
[5]
103
文献紹介 (3/3)
•
[6] Jeffrey Dean, “Challenges in Building Large-Scale Information Retrieval
Systems”, WSDM ‘09 Tutorial, 2009.
– Google の大規模検索エンジンを実現するための内部の仕組みを (一部) 解説
•
[7] llamerada の日記 (http://d.hatena.ne.jp/llamerada/): Google WSDM‘09講演翻
訳：大規模な情報検索システム構築における課題(1)-(4)
– [6]の日本語による解説
•
[8] Ricardo Baeza-Yates, Berthier Ribeiro-Neto, “Modern Information Retrieval
2nd edition“, Addison-Wesley, 2011.
– 1000ページ弱の大書．情報検索に幅広い話題を扱っている．ひとりの著者が一貫して書い
ているわけではないのでトピック毎に読むのに適している．
104
Thank you!
おしまい
105