17

「逆インデックス」、「ベクトル空間モデル」、「コサイン類似度」、「PageRank」などの考え方を含む、検索エンジンのランキングの基本を理解しています。

ただし、ユーザーが人気のあるクエリ用語を送信すると、この用語を含む何百万ものページが表示される可能性が非常に高くなります。その結果、検索エンジンはこれらの何百万ものページをリアルタイムでソートする必要があります。たとえば、Google で「バラク オバマ」と検索してみました。「約9億3700万件(0.49秒)」と表示されます。0.5 秒以内に 9 億以上のアイテムをランク付けしますか? それは本当に私の心を吹き飛ばします！

検索エンジンはどのようにして大量のアイテムを 1 秒以内に並べ替えるのでしょうか? 誰か直感的なアイデアを教えてくれたり、参考文献を指摘したりできますか?

ありがとう！

アップデート：

  1. これまでの回答のほとんど (いくつかの古い議論を含む) は、「逆インデックス」に貢献しているようです。ただし、私の知る限り、逆索引は「関連ページ」を見つけるのに役立つだけです。言い換えれば、逆インデックスによって、Google は「バラク・オバマ」を含む 9 億ページを (数十億を超えるページから) 取得することができました。ただし、これまで読んだスレッドに基づいて、これらの何百万もの「関連ページ」を「ランク付け」する方法はまだ明確ではありません.
  2. MapReduce フレームワークがリアルタイム ランキングの主要コンポーネントになる可能性は低いです。 MapReduce は、バッチ タスク用に設計されています。ジョブを MapReduce フレームワークに送信する場合、通常、応答時間は少なくとも 1 分であり、明らかに遅すぎて要求を満たすことができません。
4

11 に答える 11

8

ランキングが完全であると確信していれば、この質問は本当に関連性があります。提供される順序が概算である可能性は十分にあります。

ランキング結果の流動性を考えると、妥当に見える回答が間違っていると見なされることはありません。たとえば、Web のセクション全体が上位の結果から除外された場合、それらが後で含まれていれば気付かないでしょう。

これにより、開発者は、他のほとんどすべてのドメインではまったく利用できない自由度を得ることができます。

実際の質問は、結果が各ページに割り当てられた実際のランクとどの程度正確に一致するかということです。

于 2013-11-05T11:13:03.807 に答える
6

検索エンジンからの応答を得るのにかかる時間に影響を与える主な要因が 2 つあります。

1 つ目は、インデックスをハードディスクに保存している場合です。データベースを使用している場合、ハードディスクを少なくとも少しは使用している可能性が非常に高くなります。コールド ブートから、クエリに必要なデータがデータベース キャッシュに取り込まれるまで、クエリは遅くなります。

もう 1 つは、人気のあるクエリのキャッシュを用意することです。クエリの検索には、キャッシュから結果を返すよりもはるかに時間がかかります。現在、ディスクのランダム アクセス時間が遅すぎるため、RAM に格納する必要があります。

これらの問題の両方を解決するために、Google は memcached を使用します。これは、Google 検索エンジンの出力をキャッシュし、少し古い結果をユーザーに提供するアプリケーションです。ほとんどの場合、Web は問題になるほど速く変化しないため、これは問題ありません。また、検索が大幅に重複するためです。バラク・オバマが最近検索されたことはほぼ間違いありません。

検索エンジンの待ち時間に影響を与えるもう 1 つの問題は、ネットワークのオーバーヘッドです。Google は、Web サーバーとして使用するために最適化された Linux (IIRC) のカスタム バリアントを使用しています。彼らは、結果をクエリに変換し始めるのにかかる時間をいくらか短縮することに成功しました。

クエリがサーバーに到達した瞬間、サーバーは、Google がクエリ用語の処理を完了する前であっても、HTTP 応答のヘッダーを使用してユーザーにすぐに応答します。

彼らには他にもたくさんのトリックがあると確信しています。

編集: また、インデックス作成プロセスから、逆リストを既に並べ替えたままにします (クエリごとに処理するよりも 1 回処理する方が適切です)。

これらの事前に並べ替えられたリストでは、最もコストのかかる操作はリストの交差です。Google がベクトル空間モデルに依存していないことは確かですが、リストの交差はそれほど重要ではありません。

文献によると、最高の結果をもたらすモデルは確率モデルです。例として、Okapi BM25 を調べたいと思うかもしれません。私の研究分野 (XML 検索) では、実際にはかなりうまく機能します。確率モデルを使用する場合、一度に用語を処理するよりもドキュメントを一度に処理する方がはるかに効率的です。これが意味することは、用語を含むすべてのドキュメントのリストを取得する代わりに、各ドキュメントを調べて、クエリに含まれる用語に基づいてランク付けすることです (用語を含まないドキュメントはスキップします)。

しかし、賢くなりたいのであれば、別の方法で問題に取り組むことができます (ただし、それがより良いと思われる場合のみ)。非常にまれなクエリ用語がある場合は、最も影響が大きいため、最初にランク付けできます。次に、次善の用語でランク付けし、このドキュメントが上位 k 件の結果に含まれる可能性が高いかどうかを判断するまで続けます。

于 2013-11-04T13:24:18.713 に答える
5

考えられる戦略の 1 つは、リスト全体ではなく上位 k だけをランク付けすることです。

たとえば、100 万件のヒットから上位 100 件の結果を見つけるには、選択アルゴリズムによる時間計算量は O( n log k ) です。k = 100 およびn = 1,000,000 なので、実際には log( k ) を無視できます。

これで、 100 万件のヒットから上位 100 件の結果を取得するために必要なのは O( n ) だけです。

于 2013-10-21T14:19:34.630 に答える
1

また、RDBMS の代わりに NoSQL データベースを使用することも役立つと思います。

NoSQL データベースは水平方向のスケーリングが優れており、ボトルネックを生成しません。Google Facebook や Twitter などの大物がそれらを使用しています。

他のコメント/回答が示唆しているように、データは既にソートされている可能性があり、バッチ全体ではなく、見つかったデータのオフセットを返しています。

本当の問題は、いかに多くの結果を迅速にソートするかではなく、世界中の何千万、何億人もの人々が同時に Google にクエリを実行しているときに、どのようにソートするかです xD

于 2013-10-21T14:29:18.327 に答える
0

ここでこの質問に対する正確な回答を得られるとは期待できません ;) とにかく、考慮すべき点がいくつかあります。Google はあらゆる部分で独自のインフラストラクチャを使用しています。ネットワーク機器やデータベース ストレージの複雑さの順序を推測することさえできません。この問題のハードウェア コンポーネントについて私が知っているのはこれだけです。

ここで、ソフトウェアの実装について説明します。その名前が示すように、PageRank はそれ自体がランクです。検索クエリを入力しても、ページはランク付けされません。インフラストラクチャの完全に独立した部分で 1 時間ごとにランク付けされると思います。また、Google のクローラー ボットが 24 時間年中無休で Web をローミングしていることは既にわかっているため、新しいページは「ソートされていない」ハッシュ マップに追加され、次回のアルゴリズムの実行時にランク付けされると想定しています。

次に、クエリを入力すると、何千もの CPU が、ギャップ ファクターを使用して PageRank データベースの何千もの異なる部分を個別にスキャンします。たとえば、ギャップ係数が 10 の場合、1 台のマシンは PageRank 値が 0 ～ 9.99 のデータベースの部分をクエリし、もう 1 台は 10 ～ 19.99 のデータベースをクエリします。リソースは Google にとって障害ではないため、設定できます。各マシンが 10 万ページ未満のページをクエリできるように、ギャッピング ファクターが非常に低い (たとえば 1) ため、ハードウェアにとってはそれほど大きくありません。次に、クエリの結果をコンパイルする必要がある場合、どのマシンがデータベースのどの部分を正確にランク付けしているかを知っているため、「プールを埋める」原則を使用できます。みましょう各 Google ページのリンク数です。データベースのすべての異なる部分に対して、これらすべてのマシンで実行されたクエリから返されたページを組み合わせるアルゴリズムは、最初のn 個の結果を埋めるだけで済みます。そのため、データベースの最高ランクに対してクエリを実行しているマシンから結果を取得します。nより大きい場合は終了し、そうでない場合は次のマシンに移動します。これはO(q*g/r)しか取りません。ここで、sは Google が提供するページの数、gはギャップ係数、rは PageRank の最高値です。この仮定は、2 番目のページに移動すると、クエリがもう一度実行されるという事実によって促進されます (生成にかかる時間が異なることに注意してください)。

これは私の 2 セントにすぎませんが、この仮説はかなり正確だと思います。

編集:高次クエリの複雑さについては、これを確認してください。

于 2013-11-06T17:05:07.963 に答える
0

Google が実際に何をしているのかはわかりませんが、確かに近似値を使用しています。たとえば、検索クエリが「検索エンジン」の場合、結果の数は = (単語「検索」が 1 回以上出現するドキュメントの数 + が 1 回以上出現するドキュメントの数) になります。 「エンジン」という言葉）。これは、O(1) 時間の計算量で実行できます。詳細については、Google の基本構造http://infolab.stanford.edu/~backrub/google.htmlを参照してください。

于 2013-11-21T03:39:10.893 に答える
0

更新について:

MapReduce フレームワークがリアルタイム ランキングの主要コンポーネントになる可能性は低いです。MapReduce は、バッチ タスク用に設計されています。ジョブを MapReduce フレームワークに送信する場合、通常、応答時間は少なくとも 1 分であり、明らかに遅すぎて要求を満たすことができません。

MapReduce は、バッチ タスク用に設計されているだけではありません。Apache Spark、Storm、Infinispan Distributed Executor、 Hazelcast Distributed Executor Serviceなど、リアルタイム コンピューティングをサポートする非常に多くの MapReduce フレームワークがあります。

質問に戻る MapReduce は、クエリ タスクを複数のノードに分散し、結果をマージするための鍵です。

于 2013-11-06T16:01:05.927 に答える
-1

一言でお答えします。QuickSort です。

于 2013-11-06T18:01:21.520 に答える