4

次の検索結果を検討してください。

わかった。ページはインデックス化されており、インデックステーブルのカウントと最初の数項目を検索するだけでよいので、速度は理解できます。

ここで、AND演算を使用した次の検索について考えてみます。

これは私をカチカチさせます;）いったいどうやって検索エンジンは巨大なデータセットに対するAND演算の結果をこんなに速く得ることができるのでしょうか？私はタスクを実行するために次の2つの方法を見ます、そして両方ともひどいです：

  1. 'David'の検索を行います。巨大な臨時雇用者のテーブルを取り、その上で「ジョン」の検索を実行します。ただし、一時テーブルは「John」によってインデックス付けされていないため、ブルートフォース検索が必要です。どんなハードウェアを持っていても、0.25秒以内には計算されません。
  2. 'DavidJohn'のようなすべての可能な単語の組み合わせによる索引付け。次に、キーの数の組み合わせ爆発に直面しますが、Googleでさえそれを処理するためのストレージ容量がありません。

そして、あなたはあなたが望むだけ多くの検索フレーズを一緒にANDすることができます、そしてあなたはまだ0.5秒以内に答えを得ることができます！どのように？

4

4 に答える 4

2

MarkusがGoogleが多くのマシンでクエリを並行して処理することについて書いたことは正しいです。

さらに、この作業を少し簡単にする情報検索アルゴリズムがあります。これを行うための古典的な方法は、転置リスト（その用語を含むすべてのドキュメントの各用語のリスト）で構成される転置インデックスを作成することです。

概念的には、2つの用語を含むクエリを検索する場合、2つの用語（「david」と「john」）のそれぞれの投稿リストを取得し、それらに沿って歩き、両方のリストにあるドキュメントを探します。両方のリストが同じように順序付けられている場合、これはO（N）で実行できます。確かに、Nはまだ巨大です。そのため、これは数百台のマシンで並行して実行されます。

また、追加のトリックがあるかもしれません。たとえば、最高ランクのドキュメントがリストの上位に配置されている場合、アルゴリズムは、リスト全体をたどることなく、10個の最良の結果を見つけたと判断できる可能性があります。次に、残りの結果数を推測します（2つのリストのサイズに基づいて）。

于 2010-02-26T10:34:53.953 に答える
1

あなたは間違った角度から問題に取り組んでいると思います。

Googleは単一のマシン上にテーブル/インデックスを持っていません。代わりに、サーバー間でデータセットを大幅に分割します。レポートによると、すべてのクエリに1000台もの物理マシンが関与しています。

その量の計算能力を使用すると、すべてのマシンが数分の1秒で作業を完了することを保証することが「単純に」（非常に皮肉なことに使用されます）問題になります。

Googleのテクノロジーとインフラストラクチャについて読むことは、非常に刺激的で非常に教育的です。BigTable、MapReduce、Googleファイルシステムを読むことをお勧めします。

グーグルは彼らの技術についての多くのジューシーな情報で利用可能な彼らの出版物のアーカイブを持っています。メタフィルターに関するこのスレッドは、検索エンジンを実行するために必要な膨大な量のハードウェアについての洞察も提供します。

于 2010-02-26T10:10:26.450 に答える
1

グーグルがそれをどのように行うかはわかりませんが、クライアントが同様のものを必要としたときに私がそれをどのように行ったかをあなたに伝えることができます：

Aviで説明されているように、転置インデックスから始まります。これは、すべてのドキュメント内のすべての単語、ドキュメントID、単語、およびそのドキュメント内の単語の関連性のスコアを一覧表示した表にすぎません。（別のアプローチは、単語の各出現をその位置とともに個別に索引付けすることですが、この場合は必要ありませんでした。）

そこから、Aviの説明よりもさらに簡単になります。用語ごとに個別に検索する必要はありません。標準のデータベース要約操作では、これを1回のパスで簡単に実行できます。

SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2
ORDER BY total_score DESC

これにより、「David」と「John」の両方のスコアを持つすべてのドキュメントのIDが返されます（つまり、両方の単語が表示されます）。関連性の近似順に並べられ、実行にほぼ同じ時間がかかります。INパフォーマンスはターゲットセットのサイズにあまり影響されず、countすべての用語が一致したかどうかを簡単に判断できるため、探している用語。

この単純な方法では、「David」スコアと「John」スコアを合計して、全体的な関連性を判断するだけであることに注意してください。順序/近接などは必要ありません。考慮に入れる名前の。繰り返しになりますが、グーグルはそれをスコアに織り込んでいると確信していますが、私のクライアントはそれを必要としませんでした。

于 2010-02-26T11:34:32.050 に答える
0

私は16ビットマシンでこの数年前に似たようなことをしました。データセットの上限は約110,000レコード（墓地だったため、埋葬には限りがあります）だったので、それぞれ128Kビットを含む一連のビットマップを設定しました。

「david」を検索すると、ビットマップの1つに関連するビットが設定され、レコードに「david」という単語が含まれていることを示します。2番目のビットマップの「john」についても同じことをしました。

次に、2つのビットマップの2進数の「と」だけを実行する必要があります。結果のビットマップは、どのレコード番号に「david」と「john」の両方が含まれているかを示します。結果のビットマップをクイックスキャンすると、両方の用語に一致するレコードのリストが返されます。

しかし、このテクニックはグーグルでは機能しないので、これを私の0.02ドルの価値があると考えてください。

于 2010-02-26T09:51:12.117 に答える