Google検索エンジン初期の仕組みは論文で書かれている
Googleの創業者はご存知の通り「ラリー・ペイジ」と「セルゲイ・ブリン」の２人である。
２人はスタンフォード大学での博士課程在籍中に知り合い『検索エンジン』について共通の関心があったことから、1998年に共著で論文を執筆した。論文タイトルは『The Anatomy of a Large-Scale Hypertextual Web Search Engine（大規模なハイパーテキスト的なウェブ検索エンジンに関する解剖）』。
この論文では、Googleの検索エンジンのインデックスや検索順位決定のベースとなった考え方が詳しく解説されている。「こんなに載せてしまっていいの？」と不安になるレベルで詳しく書かれている。
SEO対策の前に論文を読んでおこう
この論文は、スタンフォード大学の情報研究室のWebサイトから参照することができる。名論文であるのに関わらず、ネットで探しても日本語で読める要約等は見つからなかった。
この論文内容を読むことにより、検索エンジンの理解、さらにはWebサイトの正しいSEO対策の理解にもつながるかもしれない。この記事では、論文の要約と、簡単な解説・考察をまとめる。
意訳した部分が多くあること、個人的な判断で重要だと思われる部分を太字等で強調していることにご留意ください。
当時の検索エンジンの普及状況
- Web上の情報は急速に増加中
- 人々は検索エンジンで何かを調べるというよりも、リンクを飛んでいくことでネットサーフィンをすることが多かった
- Web上の高品質なインデックスは、人の手により管理されていた
- 自動の検索エンジンは、あまりにも低品質の検索結果ばかり表示しており、中には、検索エンジンを欺き、上位表示させるような広告主もいた
- Googleはこれらの問題に対処できるような大規模検索エンジンを構築することにした
(1. Introductionより）
1998年当初の、ラリー・ペイジとセルゲイ・ブリンの検索エンジンに対する問題意識が書かれています。検索エンジンを欺くようなSEO対策をする人は（随分減ったものの）未だにいますね。
Googleの検索エンジンの目的
Web検索エンジンの品質を向上させる
- ユーザーが本当に興味のある結果が、しばしば役立たずの結果に埋もれてしまっている
- Googleにとっては、"関連性がある"という概念は、"最高品質のドキュメントのみを検索結果に含める"ということ
- 検索結果の精度をとことん高めることは、検索結果数の規模（システムが返すことができる関連文書の総数）よりずっと重要
- Webの規模が拡大し、Web上のドキュメント数が増えれば増えるほど、検索エンジンの精度は重要になる
(1.3.1 Improved Search Qualityより)
1998年当時は「検索エンジンは、より多数のページをインデックスし、結果表示できるモノこそが最強」という考え方がメジャーだったようです。そんな中、グーグルは「いや、検索の"規模"よりも"精度"を高めることが大事やろ」と考えていたわけですね。
学術研究をサポートする
- ここ5年くらいで（1993〜1997年）Webおよび検索エンジンは、学術分野よりも商用分野がメジャーとなってきた
- 現状、他の検索エンジンは、企業により運営されており、技術的な仕組みがほとんど公開されていない⇒ブラックボックス化されており、広告主義的
- Googleには「大規模なWebデータを活用することにより、学術領域の発展を促進する」という目標がある
- 研究者たちがすぐにWebへアクセスでき、大量のデータを参照でき、それなしでは成し遂げられなかったような素晴らしい研究成果が生まれるようなアーキテクチャを作りたい
- 研究者が、またたとえ学生であっても、大規模なWebデータを用いて素晴らしい実験を提案でき、そして実行できるような環境を整える
（1.3.2 Academic Search Engine Researchより）
Googleはもともと研究室のプロジェクトから生まれたこともあるでしょうが、学術研究のサポートすることを大きな目標としています。論文検索のGoogle Scholarなんかは、まさにこの目標から生まれたものでしょう。
Googleという名前の意味
- Googleという名前は「googol」から生まれた
- この名前は「超大規模な検索エンジンを構築する」という創業者2人の理念に合っている
(1. Introductionより）
googolとは極めて大きい数字の単位のことであり、1googol＝「10の100乗」です。実際には、ラリー・ペイジがgoogolの綴りを間違えたことから「google」になったというのは有名な話です。
Googleの検索エンジンの考え方
- Googleが（当時の）他の検索エンジンと異なっているのは、ハイパーテキストの付加構造を存分に活用する点である (1. Introductionより）
- リンク構造とリンクのアンカーテキストは、関連性の判断と品質フィルタリングに活用できる（1.3.1 Improved Search Qualityより）
当時、他の検索エンジンが、基本的にキーワードマッチングによりシンプルに関連度を算出していた中、Googleは「Web Page同士のリンクの繋がりや、リンクのテキストにより関連度を計算できる」と考えました。
Googleの考える快適な検索エンジンの条件
- 膨大な数のWebドキュメントを収集し、最新の状態に保つためには、高速クロール技術※が欠かせない
- 膨大な数の索引（場合によってはドキュメントも）を保管するためには、保管スペースを効率的に使用する必要がある
- クエリ※に対しては（数百から数千/秒の速さで）迅速に処理する必要がある
- Googleは今後も拡大していくであろうWebの成長を考慮し、非常に大きなデータセットに対応できるように設計されている
（1.2. Google: Scaling with the Webより）
※クロールとは：ソフトウェアなどが自動でWebページを巡回してデータ収集する作業のこと
※クエリとは：データベース管理システムに対する処理要求のこと。ここでいうクエリは、ユーザーが『検索したいキーワードの組み合わせを入力』することで『このキーワードに関するページ結果を表示してください』というリクエストのことですね。
ここからは少し技術的な話になります。Webページを高速で巡回し、保管スペースを効率的に利用して、ユーザーが検索したら迅速に検索結果を返すことが検索エンジンには欠かせないということですね。
いかにして検索結果に優先順位をつけるか
検索結果の精度を高めるためのGoogleの2つの大きな特徴
- ウェブのリンク構造を利用して、各ページの品質を計算すること。この品質はページランクと呼ばれる
- リンクを利用することで検索結果を改善すること
（2.1 PageRank: Bringing Order to the Webより）
ページランクの考え方
もともとGoogleは、各ページのページランクを公表していましたが、2016年になってその機能を完全に廃止しました。とはいえ、公表がされなくなっただけで、ページランクの考え方は、今も検索順位に大きな影響を与えていると考えられます。そのため、ページランクがどのような仕組みで動いていたのか知っておくのは有用でしょう。
- 「Webの引用リンク構造」は、既存のウェブ検索エンジンではほとんど使われていない重要なリソース
- 引用における重要度という客観的指標は、人々の主観的な重要度のとらえ方に近い
- Googleでは、膨大な数のハイパーリンクを含む引用構造マップを作成し、これによりページランクを迅速に計算する
- キーワードをシンプルにWebページのタイトルとマッチング検索した上で、ページランクにより表示結果に優先順位をつけるだけでも検索エンジンに質は高くなる
（2.1 PageRank: Bringing Order to the Webより）
Web上のリンクの繋がりからページランクを計算し、これを上位表示すべきWeb ページを決めるのに利用するということですね。
ページランクの計算の考え方
- 学術引用文献の場合、おもに「特定のページへの引用数」や「バックリンク数」を数えることによってWebでの評価が行われてきた
- Googleのページランクでは、これに加えて「すべてのページからのリンクを同等にはカウントせず」「ページ上のリンク数により標準化する」ことで精度を上げる（詳細は以下）
（2.1.1 Description of PageRank Calculationより）
学術研究の世界では「掲載論文が特定の期間内にどれくらい頻繁に引用されたか」を平均値で計算することで、ジャーナルの影響度を測ります。Googleでは「1リンク＝1引用」と単純にカウントするのではなく、同じリンクでも状況に応じてリンクの重み付けを変えることで、より精度を高めています。
ページランク計算の手法
・ページAは、T1 ... Tnのページから引用されていると仮定する
・パラメータdは減衰係数で、0〜1の間で設定
（通常はd=0.85に設定）
・また、C(A)は、ページAから出て行くリンクの数として定義される
・ページAのページランクは、以下のように求められる。
PR(A) = (1-d) + d ( PR(T1) / C(T1) + ... + PR(Tn) / C(Tn) )
- ページランクはWebページ全体を通して確率分布を形成するため、全Webページのページランク合計は1になる
- ページランクは、単純な反復アルゴリズムを用いて計算することができ、Webにおける正規化されたリンク行列の主固有ベクトルと一致する
- 無作為にWebページを与えられ、リンクをクリックし続けるランダムサーファー（仮定）がいるとして、ランダムサーファーはそのページを訪れる確率＝そのページの「ページランク」
- 減衰係数d＝各ページにおいて、ランダムサーファーが退屈して、別のページを要求する確率
- 減衰係数dはページごと、あるいはページのグループごとに加算するため、ユーザーごとのパーソナライズも可能になる上、システムを欺いてランキング上位を獲得することが難しくなる
（2.1.1 Description of PageRank Calculation、2.1.2 Intuitive Justificationより）
つまるところ
・ページランクの高いWebページからリンクされる方が、ページランクは高くなる
・貼ってあるリンク数が少ないWebページからリンクされる方が、ページランクは高くなる
（リンクがベタベタ貼ってあるページからリンクされることの効果は薄い）
・引用してくれているページが多数あるほどページランクは高くなる
・引用してくれているページのページランクが高いほど、引用されたページのページランクは高くなる
ということですね。怪しげなサイトよりもYahooに引用された方がページランクが高くなるのは合理的なことでしょう。
アンカーテキストの扱いについて
- 当時の他の検索エンジンは、リンクのテキストを、そのリンクが貼られているページに関連付ける
- Googleではこれに加えて、リンク先のページに、リンクテキストを関連付ける
（2.2 Anchor Textより）
たとえば、『検索順位を上げるSEO対策をイチから図解』というタイトルの記事があります。この記事に対して、あるページから『検索エンジンのアルゴリズムについてはこちら記事が参考になります』というリンクを貼れば、"検索エンジン"、"アルゴリズム"というキーワードもこの記事に関連しているのだとGoogleは認識するわけです。
リンク先のページにリンクテキストを関連付けるメリット
- アンカーテキストは、そのページに対する信頼性の高い記述を提供する
- 画像、プログラムなど検索エンジンによってインデックスすることができないドキュメントに対するアンカーを読み取ることができる（クロールされていなかったページを検索結果に入れることができる）
（2.2 Anchor Textより）
3. その他、検索順位決定に利用できる指標
- Googleでは、単語のフォントサイズなどの視覚的な表現まで考慮する
- より"大きい"orより"太い"フォントの単語は、他の単語より重み付けが大きい
（2.3 Other Featuresより）
より大きな見出しに含まれているキーワードや、太文字に強調されたキーワードを、Googleは重要だと判断します。SEO対策としては、上位表示したいキーワードを見出しに入れたり、太字化することは有効だと言えるでしょう（過度に実行すると逆効果の可能性もあります）。
Googleの検索エンジンに対する姿勢
- 他の検索エンジンに利用されているような標準的なベクトル空間モデルでは、クエリとドキュメントが出現する単語により定義されたベクトルであるため「検索キーワード（クエリ）が最も近似しているドキュメント」を結果として返す
- この方法では、クエリに数語足されたような、短いドキュメントばかりが検索結果に表示されてしまう
- 「ユーザーが調べたいことをより正確に指定して検索するべきだ」という意見もあるが、Googleはこれに真っ向から反対する
- 検索されたトピックについての膨大な量の高品質情報ができるのだから、それらを効率的に見つけれるような検索エンジンにするべきだ
（3.1 Information Retrievalより）
Googleの検索エンジンのアルゴリズム
アルゴリズム概要
Googleのアーキテクチャイメージ
クロールの流れ
- URLサーバーが巡回すべきURL一覧をクローラーに送信する
- クローラーにより巡回（フェッチ※）されたWebページは、保管サーバーに送信される
- 保管サーバーは、各Webページに文書IDを割り当てた上で、ページ情報を圧縮してリポジトリ※に格納する
（4.1 Google Architecture Overviewより）
※フェッチ：データベースのデータを読み込み、参照すること
※ リポジトリ：データや情報などが体系立てられた上で保管されている場所
ここまでは、イメージがしやすいですね。リポジトリには「docID」「ページURL」「ページのテキスト」「ダウンロード日時」などが記憶されます。
インデックス〜クエリへの応答までの流れ
- インデックスは、主に「インデクサ」と「ソータ」によって実行される
- インデクサは、リポジトリを読み込み、ドキュメントの解凍を行い、構文解析する
- インデクサは、解析により得られたそれぞれの単語に、単語ID をつけて辞書（レキシコン）を作成する
- さらにインデクサは単語情報（「単語」「その単語のドキュメント内の位置」「おおよそのフォントサイズ」「大文字小文字の使用」など）をバレルに保存する
- バレルでは、これらの単語情報を持つフォーワードインデックス※が作成される
- ソータは、バレルを読み込み、文書IDによりソートされているものを、単語IDにより再ソートし、転置インデックス※を生成する
- ソータは、転置インデックス内に、単語IDリストとオフセットリストを生成
- インデクサは、すべてのWebページのすべてのリンクを解析し、その情報をアンカーファイルに保存する（このファイルには「リンクのテキスト」と「どのリンクがどこを指しているのか」を判断するための情報が入っている）
- URLリゾルバは、アンカーファイルを読み取り、相対URLを絶対URLに変換した上で、文書IDへと変換
- URLリゾルバは、さらにアンカーテキストを、アンカーが指し示す文書IDと結びつけた上で、フォーワードインデックスに送る
- また、URLリゾルバは「文書IDのペアであるリンク」のデータベースを生成する。リンクデータベースは、すべてのドキュメントのページランクを計算するために使用される
- DumpLexiconと呼ばれるプログラムが、インデクサによって作成されたレキシコンと合わせてこのリストを取得し、サーチャーによって使用される新しいレキシコンを生成する
- サーチャーはWebサーバーによって実行され（ユーザーが検索することで実行）、転置インデックス、ページランク、DumpLexiconで作成されたレキシコンを使用してクエリに応答する
（4.1 Google Architecture Overviewより）
※フォーワードインデックス：説明をするとかなり長くなりそうなので、こちらのページを参照すると良いと思います。このページの説明では、転置インデックスにするために表をひっくり返していますが、そのひっくり返す前の状態がフォーワードインデックスにあたりますね。
※ 転置インデックス：転置インデックスとは、全文検索を行う対象となるドキュメント群から単語の位置情報を格納するための索引構造のことです。イメージとしては、本の巻末にある索引のようなものですね。
複雑になってきました。整理すると、
- インデクサは、色んな働きをします。重要な働きは次の2つ。①ドキュメントの解析をして辞書（レキシコン）を作成します。このレキシコンというのは、単語が並んだ語彙表のようなイメージです。②リンク情報を解析します。
- バレルにおいて、フォーワードインデックスが作成されます。
- ソータは、フォーワードインデックスから転置インデックスを作成します。
フォーワードインデックスというのは文書IDをキーとして、ページ情報が保存されています。一方で、転置インデックスは、単語IDをキーとして情報が保存されています。実際に検索が行われるときには単語が入力されて行われますので、検索がしやすいように、フォーワードインデックスから転置インデックスを作成するわけです。
このあたりの流れについては、以下のWebサイトで非常に分かりやすく説明されています。上記の説明より理解しやすいと思うので、いまいちよく分からなかった方は一度読んでみると良いでしょう。
インデックスについての詳細
構文解析、バレルへのインデックス、ソータの働きについては詳細も書かれていたので載せておきます。（4.4 Indexing the Webより）
構文解析（パース）について
- Web上で広く動作するパーサは、エラーが発生する恐れのある膨大な配列を処理する必要がある
- これらのエラーには、HTMLタグのタイプミス、ASCII以外の文字、数百にも入れ子になったHTMLなど、無数の種類あり
- Googleでは、最高の速度を実現するために、flexを使用して語彙解析ツールを生成
- 妥当な速度で動作し、かつ非常に堅牢なパーサーを開発するのはかなり大変
パーサとは複雑な構造のテキスト文書を解析し、プログラムで扱えるようなデータ構造の集合体に変換するプログラムのことです。無数のバリエーションを持つWebページを解析するのが大変というのは、想像に難くないですね。
バレルへのインデックスについて
- パースされたドキュメントは、多数のバレルにエンコードされる
- すべての単語は、インメモリハッシュテーブルを使用することにより、単語IDに変換される
- レキシコンハッシュテーブルへの新規追加は、ファイルに記録される
- 単語が単語IDに変換されると、ドキュメント内の各単語の出現がヒットリストに変換され、フォーワードバレルに書き込まれる
- インデックスフェーズを並列化する上での大きな難点は、レキシコンを共有する必要があることだった
- Googleでは「レキシコンを共有するのではなく、1400万語に固定されたベースのレキシコン上には無い単語を全てログを書き込む」というアプローチを取ることにした
- それにより、複数のインデクサを並行して実行することができ、追加単語が書き込まれた小さなログファイルを、1つインデクサで処理することができる
レキシコンというのは、先程もちょっと説明しましたが、辞書であり語彙表のことです。単語がひたすら並んでいるイメージですね。複数のインデクサを同時に実行しようとすると、それらの複数のインデクサからレキシコンに書き込めるように共有する必要があります。これは効率が悪いということで、Googleではベースとなる語彙を一定数決めておき、そこには載っていない単語をそれぞれのインデクサが新しく追加していく、という方法をとったのですね。
ソータの働きについて
- 転置インデックスを生成するために、ソータはそれぞれのフォーワードバレルを取り込み、単語IDでソートして、タイトルとアンカーヒットとフルテキストの転置バレルを作成する
- このプロセスは、同時には1バレルしか発生しないため、一時的な保管はほとんど必要ない
- また、Googleでは、異なるバケットを同時に処理できるよう複数のソータを利用して並行的にソートフェーズを実行する
- バレルはメインメモリに収まらないため、ソータは単語IDと文書IDに基づいてメモリに収まるバスケットにさらに細分化する。
- その後、ソータは、各バスケットをメモリにロードした上でソートし、その内容を転置バレルに書き込む
転置インデックスが作成されるイメージについては「転置索引とは何か？」を読むとよく分かります。
主なデータ構造についての詳細
ここはやや複雑なので、読み飛ばしても良いでしょう。
- Googleのデータ構造は最適化されているため、大規模なドキュメント群をわずかなコストでクロール、インデックス、検索することができる
- ディスクシークを完了するのには未だに約10ミリ秒が必要になってしまう。そのため、 Googleでは可能な限りディスクシークを避けるように設計されいる
（4.2 Major Data Structuresより）
リポジトリ
図2. リポジトリのデータ構造
- リポジトリには、すべての圧縮されたWebページの完全なHTMLデータが含まれている
- リポジトリでは、ドキュメントは順番に格納され、図2に示すように文書ID、文書の長さ、URLにより接頭辞が付けられる
- Googleではリポジトリと、クローラー・エラーの一覧ファイルさえあれば、他のすべてのデータ構造を再構築することができる
（4.2.2 Repositoryより）
ドキュメントインデックス
- ドキュメントインデックス（docIndex）は、各ドキュメントに関する情報を保持
- Index Sequential Access Mode（索引付き順次アクセス方式）によるインデックスであり、文書IDで順序が付けられている
- 格納される情報には、現在のドキュメントステータス、リポジトリへのポインタ、ドキュメントチェックサム、様々な統計情報が含まれる
- ドキュメントが既にクロールされている場合は、ドキュメントのURLとタイトルの情報を含む文書情報へのポインタも含まれている
- クロールされていないない場合は、ポインタはURL情報のみを含むURLリストを指し示す
（4.2.3 Document Indexより）
ヒットリスト
図3. フォーワードインデックス/転置インデックス
- ヒットリストは、位置、フォント、大文字表記情報などを含む「特定のドキュメント内の、特定の単語の出現のリスト」（図3のようなイメージ）
- ヒットリストは、フォーワードインデックスと転置インデックス両方の大部分を占めるデータ
- そのため、できるだけ効率的に表現することが重要
- Googleでは、単純な符号化よりはるかに少ないスペースで済み、ハフマン符号化よりもはるかに少ないビット操作で済む「圧縮符号化」を利用
- フォントサイズは、ドキュメント内の他の部分に対する相対値として表される
（4.2.5 Hit Listsより）
ヒットリストとレキシコンの関係について、少し噛み砕いて説明すると、レキシコン（辞書）には「単語」情報が入っており、ヒットリストには「どこのドキュメントのどこに、どんな装飾状態でその単語が入っているか」という情報が入っています。レキシコンには「この単語は、どのヒットリストに対応しているか」という情報も入っているので、２つをつなぎ合わせることができます。
例えば「SEO」というキーワードを探す場合、まずレキシコン内で「SEO」という単語を見つけます。それから「SEO」に対応するヒットリストを見つけ「SEOという単語はこのドキュメントの、何文字目に、このくらいのフォントサイズで含まれている」ということが分かるのですね。
フォワードインデックス
- フォーワードインデックスは、部分的にソートされている
- フォーワードインデックスは、多数のバレルに格納されており、各バレルには単語IDの範囲が決まっている
- ドキュメントに特定のバレルに該当する単語が含まれている場合、まず文書IDがバレルに記録され、その後にその単語に対応するヒットリストを持つ単語IDのリストが記録される（この方法が最も効率的とのこと）
（4.2.6 Forward Indexより）
転置インデックス
- 単語一覧の辞書（レキシコン）には、単語IDの対応するバレルへのポインタが含まれている
- このポインタは、対応するヒットリストと共に、文書IDの文書リストを指す（この文書リストは、全ドキュメントにおける全単語の出現を示す）
- 重要な問題は、文書IDが文書リストにおいてどのような順序で表されるべきか、ということ。
- 1つめの方法は、文書IDによりソートして格納する方法。これにより、複数の単語クエリに対して異なる文書リストを迅速にマージすることができる。
- ２つめの方法は、各ドキュメント内の単語出現のランキングによりソートして格納する方法。これにより、1語のクエリに対する回答が簡単になる上、複数単語の組み合わせのクエリに対する回答がリストの始まりに近くになる。しかし、この方法ではマージが困難で、ランキング機能を変更するにはインデックスを再構築する必要がある
- Googleでは、これらの選択肢の中で妥協点を選び、2セットの転置バレルを保持。1つは、タイトルやアンカーヒットを含むヒットリスト向けのセット。もう1つは全ヒットリスト向けのセット。
- この方法では、まず最初のバレルセットをチェックし、それらのバレル内で十分に一致しなければ、より大きなバレルをチェックする
（4.2.7 Inverted Index）
クロールの仕組み
- 膨大な数のWebページに対応するために、Googleは高速分散クロールシステムを持っている
- 1つのURLサーバーは、複数のクローラーにURLのリストを提供する
- URLサーバーとクローラーはどちらもPythonで実装されており、各クローラーは一度におよそ300もの接続を保つ
- クロールにおいて、主にパフォーマンスの負荷となるのはDNSルックアップ
- Googleでは、各クローラーは独自のDNSキャッシュを保持しているため、各ドキュメントをクロールする前にDNSルックアップを行う必要はない
- Webページおよびサーバーは、多種多様であるため、インターネットの大部分で実際に実行することなしに、クローラーをテストすることは事実上不可能
- Web全体のうち1ページだけで発生するかもしれない曖昧な問題が常に数多くあり、クローラーがクラッシュしたり、予測できない不正な動作が発生したりしてしまう可能性が常にある
- クローラーにように、インターネットの多くの部分にアクセスするシステムは、この上なく堅牢に設計されなければならない。
- また、問い合わせのメールをよく読み、発生した問題を解決できるだけの多大なリソースが必要
（4.3 Crawling the Webより）
GoogleのWebページの巡回システムについてちょっと詳しく書かれています。膨大な数の、それも様々なタイプのWebページを読みにいくので、当然、予測のできないようなエラーが発生してしまうのですね。
検索のしくみ
Google検索の大まかなプロセス
- クエリを解析（パース）
- 検索された単語を単語IDに変換する
- 全ての単語について、短バレル内の文書リストの開始点を探す
- すべての検索語句に一致する文書が見つかるまで、文書リストをスキャンする
- ドキュメントのランクを計算
- 短バレル上の何らかの文書リストの終わりいる場合、完全なバレル上の文書リストの開始点を探し、ステップ4に進む
- 文書リストの終わりにいない場合は、ステップ4に進む
- マッチするドキュメントをソートし、上位k件を返す
（4.5 Searching 図4. Googleクエリの評価）
ざっくりというと、単語を単語IDに変換した上で、保存されていた文書リストからマッチするものを探すという流れです。
検索についての詳細
- 応答時間に制限を設けるために、特定の数の一致するドキュメントが見つかると、サーチャーは自動的に図4のステップ8に進む
- これは、最適ではない結果が返される可能性があるため、この問題を解決する方法を検討中（当時）。
- Googleでは、一般的な検索エンジンよりもWebドキュメントに関する情報を多く利用して検索順位を決定する（単語の出現位置、フォント、および大文字表記情報、アンカーテキスト、ページランクなど）。
- これらの全情報をランキングにまとめるのは難しく、Googleでは、ある特定の要素があまりに大きな影響を及ぼさないようにランキング機能を設計している
（4.5 Searchingより）
様々な指標をバランス良くみることで、検索順位を決めているということですが、この
指標の種類はこの論文が書かれた頃から、また随分と増えていることでしょう。
1単語のクエリに対する応答
- 1単語のクエリでドキュメントをランク付けするために、Googleはその単語のヒットリストを調べる
- タイトル、アンカー、URL、フォントサイズなどの各タイプは、個別の評価ウェイトを持っている
- 各タイプのウェイトは、タイプによりインデックスされたベクトルを作る
- Googleはヒットリストの各タイプのヒット数を数える
- その後、すべての評価カウントは、カウントウェイトへと変換される
- カウントウェイトは、最初はカウントに伴い直線的に増加するが、すぐに減少していくため、一定以上のカウントでは役立たない
- そこで、カウントウェイトのベクトルのドット積をタイプウェイトのベクトルでとり、ドキュメントのIRスコア（情報検索スコア）を計算する
- 最後に、IRスコアをページランクと組み合わせてドキュメントの最終ランクを得る
（4.5.1 The Ranking Systemyより）
複数単語のクエリに対する応答
- 複数単語の検索は、1単語検索より複雑
- 複数のヒットリストを一度にスキャン。ドキュメント内で近接して出現するヒットは、離れて出現するヒットよりも高く重み付けする
- 複数のヒットリストからのヒットは、近接するヒットが一緒になるようにマッチングされる
- マッチングされた全ヒットのセットに対しては、近接度が計算される。近接度は、ドキュメント（またはアンカー）内のヒットの距離に基づいており、10の異なるの値（ビン）にクラス分けされる
- 評価カウントは、全ヒットのタイプ（タイトル、アンカー、URL、フォントサイズ）についてだけでなく、近接度についても計算される
- すべてのタイプと近接ペアは、タイププロックスウェイト（近接度合いの重み付け）を持つ
- 評価カウントはカウントウェイトに変換され、カウントウェイトとタイププロックスウェイトの内積を取ってIRスコアを計算する
（4.5.1 The Ranking Systemより）
システムパフォーマンスを上げるためにGoogleがやっていること
ストレージの効率的な使用について
- Googleは、ウェブが成長するにつれて、同パフォーマンスあたりにかかるコストが小さくなるように設計されている
- そのうちの1つのは、ストレージを効率的に使用すること
Googleのストレージの内訳（当時）
（Table 1. Statisticsより）
システムパフォーマンスを上げるための試み
- Googleの主な作業はいわば、クロール、インデックス作成、ソートの3つ
- クロールに要する時間を予測することは困難です。なぜなら、ディスクがいっぱいになったり、ネームサーバーがクラッシュしたり、その他にもシステムを停止させるような問題が発生するため
- インデクサがボトルネックにならないように、Googleでは十分に最適化を行った。（ドキュメントインデックスへの一括更新と、重要なデータ構造のローカルディスク上への配置など）。
- インデクサとソータは完全に並行して実行される
（5.2 System Performanceより）
検索でのパフォーマンスを上げるために
- Googleでは、クエリキャッシュや、共通用語のサブインデックスなどのいわゆる一般的な最適化は行っていない（現在は不明）
- Googleでは、負荷分散や、ハードウェア、ソフトウェア、アルゴリズムの改善・向上を通じてスピードアップを図る
- Googleの目標は、毎秒、数百ものクエリを処理できるようにすること
（5.3 Search Performanceより）
当時の検索のクエリ時間例
（Table 2. Search Times）
結論
- Googleはスケール可能な検索エンジンとして設計されている
- 第一の目標は、急速に成長するWWW上で高品質の検索結果を提供すること
- Googleは、ページランク、アンカーテキスト、近接情報など、検索品質を向上させるためにさまざまな手法を採用
(6. Conclusionsより）
これからやるべきこと（当時）
- 大規模Web検索エンジンは、複雑なシステムであり、まだやるべきことがたくさんある
- 目下の目標は、検索効率を向上させ、およそ1億のWebページに対応すること
- 簡単に効率改善する方法には、クエリキャッシング、スマートディスクの割り当て、サブインデックスなどがある
- また「更新」については、まだ多くの研究をする必要がある。どの古いWebページを再クロールし、新しいWebページをクロールするかを決めるスマートなアルゴリズムが必要
- 語幹認識の処理など、商用検索エンジンでサポートされているシンプルな機能を追加していく予定
- 位置情報などのユーザーコンテキストと、検索結果の要約についても対応を行っていく予定
- リンク構造とリンクテキストの使用を拡張するように取り組んでいる
- リンクテキストについてはリンクテキストそれ自体に加えて、リンク周辺のテキストを使用する実験をしていいる
- ユーザーによるお気に入りやブックマークの重み付けを大きくすることでページランクをパーソナライズすることができるかも
（6.1 Future Workより）
このあたりは論文執筆当初のことなので、現在ではその多くが対応されています。そして、もちろんここに載っていない取り組みも多く行われていますね。
研究ツールというGoogleのビジョン
高品質の検索エンジンであることに加えて、Googleは研究ツールでもあります。 Googleが収集したデータは、すでに他の多くの論文が会議などに提出されています。
また、Googleは有用な研究ツールだけではなく、幅広いアプリケーションに欠かせないツールです。 私たちは、Googleが世界中の検索者と研究者のためのリソースとなり、次世代の検索エンジンテクノロジーを呼び起こすことを願っています。
（6.4 A Research Toolより）
最後に
リンクは重要
ここまで、論文の内容をまとめてきましたが、とにかく強調されていたのが「Googleはリンクの繋がりや、リンクのアンカーテキストをよく見ていますよ」ということ。とはいえ、この論文はGoogleが生まれた初期のもので、そのアルゴリズムは大きく変わっているはずです。検索順位に影響する指標の数も増えているでしょうし、インデックスの仕組みもより効率的になっていることでしょう。
質の高いコンテンツを作ることが長期的に有効なSEO対策になる
とはいえ、ラリー・ペイジとセルゲイ・ブリンは、Googleを作った当初から「ユーザーにとって有益な、質の高い検索エンジンを作ること」が何より大事だと論文中でしつこく主張しています。Googleを信じるなら、Webサイト運営者やライターにとって、最も持続的かつ効率的なSEO対策は「ユーザーが求めている、ユーザーのためになるコンテンツを作ること」でしょう。Googleはこれからも高品質な情報がユーザーに届くように進化し続けていくはずです。
また、より詳しく検索エンジンの仕組みについて知りたければ「検索エンジン自作入門」を読んで見るとよく分かると思います。