Google検索エンジンの原理

本稿では、ハイパーテキスト アプリケーションで広く使用されている大規模検索エンジンのプロトタイプである Google を紹介します。 Google はウェブを効率的にクロールしてインデックスするように設計されており、そのクエリ結果は他の既存のシステムよりも優れています。このプロトタイプの全文およびハイパーリンク データベースには、少なくとも 2,400 万の Web ページが含まれています。 http://google.stanford.edu/ からダウンロードできます。

検索エンジンの設計は難しい作業です。検索エンジンは、非常に多様な用語を多数含む何億もの Web ページをインデックスします。そして毎日何千もの質問に答えます。インターネット上での重要性にもかかわらず、大規模な検索エンジンは学術界ではほとんど研究されていません。さらに、技術の急速な発展とウェブページの大幅な増加により、現在では検索エンジンの構築は3年前とはまったく異なります。

この論文では、私たちの大規模な検索エンジンについて詳しく説明します。私たちの知る限り、これほど詳細に説明した公開論文はこれが初めてです。従来のデータ検索技術をこのような膨大な数の Web ページに適用する際に発生する問題に加えて、検索結果を向上させるためにハイパーテキスト内の追加情報を使用することなど、多くの新たな技術的課題があります。

本稿では、この問題を取り上げ、ハイパーテキスト内の追加情報を活用して大規模な実用的なシステムを構築する方法について説明します。インターネットでは、誰でも自由に情報を公開できます。これらの整理されていないハイパーテキストのコレクションを効果的に処理する方法も、この記事で焦点を当てている問題です。

キーワード World Wide Web、検索エンジン、情報検索、PageRank、Google

1 はじめに

Web は情報検索に新たな課題をもたらしました。 Web 上の情報量は急速に増加しており、同時に、Web の経験がない新しいユーザーが Web の芸術を体験するために絶えず訪れています。人々は、通常、重要な Web ページや Yahoo などの検索エンジンから始めて、ハイパーリンクを使用してインターネットを閲覧することを好みます。このリストには、私たちが関心のあるトピックが効果的に含まれてはいるものの、主観的であり、作成と維持にコストがかかり、更新に時間がかかり、すべての重要なトピックを網羅しているわけではありません。キーワードベースの自動検索エンジンでは、品質の低い一致が多すぎることがよくあります。問題をさらに悪化させるのは、人々の注目を集めるために、自動検索エンジンを誤誘導するためにあらゆる手段を講じる広告があることです。私たちは、既存のシステムの多くの問題を解決する大規模な検索エンジンを構築しました。ハイパーテキスト構造の適用により、クエリの品質が大幅に向上します。私たちは、10 の 100 乗を意味する googol という一般的な綴りにちなんで、このシステムを Google と名付けました。これは、大規模な検索エンジンを構築するという私たちの目標と一致しています。

1.1 インターネット検索エンジンの拡張:

1994 ～ 2000 年 Web の急激な成長に対応するために、検索エンジン テクノロジーを大幅に拡張する必要がありました。
1994 年、最初の Web 検索エンジンである World Wide Web Worm (WWWW) は、110,000 の Web ページと Web ドキュメントを検索できるようになりました。
1994 年 11 月までに、主要な検索エンジンは 2,000,000 件 (WebCrawler) から 100,000,000 件 (Search Engine Watch) の Web ドキュメントをインデックス化したと主張しました。
2000 年までに、検索可能な Web ページの数は 1,000,000,000 を超えると予測されます。同時に、検索エンジンのトラフィックも驚くべき速度で増加します。
1997 年 3 月と 4 月、World Wide Web ワームは 1 日あたり平均 1,500 件のクエリを受信しました。
1997 年 11 月、Altavista は 1 日あたり約 2,000 万件のクエリを処理していると述べました。インターネットユーザーの増加に伴い。
2000 年までに、自動検索エンジンは 1 日あたり数億件のクエリを処理するようになります。私たちのシステムの設計目標は、品質やスケーラビリティなど多くの問題に対処し、膨大な量のデータに対応できるようにスケーリング検索エンジン技術を導入することです。

1.2 グーグル:

Web に合わせた拡張 今日の Web に合わせて拡張できる検索エンジンを構築するには、多くの課題があります。 Web クロール テクノロジは、Web ページの変更速度に対応できる (最新の状態に保つ) のに十分な速度である必要があります。インデックスとドキュメントを保存するために必要なスペースは十分に大きくなければなりません。インデックス システムは、数千億件のレコードを効率的に処理できる必要があります。クエリ処理は高速でなければならず、1 秒あたり数百から数千に達する必要があります。 Web が成長し続けるにつれて、これらのタスクはますます困難になっていきます。ただし、ハードウェアの実行効率とコストも急速に増加しており、これらの困難を部分的に相殺することができます。ディスクのシーク時間やオペレーティング システムの堅牢性など、注目すべき他の要素がいくつかあります。 Google を設計するにあたり、私たちは Web の成長率とテクノロジーの進化の両方を考慮しました。 Google の設計は、膨大なデータセットを処理できるほど拡張性に優れています。ストレージスペースを効率的に使用してインデックスを保存できます。最適化されたデータ構造により、高速かつ効率的なアクセスが可能になります（セクション 4.2 を参照）。さらに、クロールされるテキスト ファイルと HTML ページの数に比べて、ストレージとインデックス作成のコストが可能な限り低くなるようにしたいと考えています (付録 B を参照)。 Google のような集中型システムの場合、これらの対策により、満足のいくスケーリング特性が得られます。

原題: Google 検索エンジンの原理

キーワード: GOOGLE