10

Google トレンド (または Twitter のような大規模なトレンド機能) の背後にあるシステム設計を理解しようとしています。

課題:

  • トレンドを計算するために大量のデータを処理する必要があります。

  • フィルタリングのサポート - 時間、地域、カテゴリなどによる

  • アーカイブ/オフライン処理のために保存する方法が必要です。フィルタリングのサポートには、多次元ストレージが必要になる場合があります。

これが私の仮定です (私は MapReduce/NoSQL テクノロジの実際の経験がありません)。

ユーザーからの各検索項目は、保存されて最終的に処理される一連の属性を維持します。

タイムスタンプ、検索地域、カテゴリなどによる検索のリストを維持するだけでなく、

例：

Kurt Cobain用語を検索しています:

Kurt-> (Time stamp, Region of search origin, category ,etc.)

Cobain-> (Time stamp, Region of search origin, category ,etc.)

質問：

  • 検索語の頻度を効率的に計算するにはどうすればよいですか?

  • 言い換えれば、大規模なデータ セットが与えられた場合、分散型のスケーラブルな方法で上位 10 の頻度の高いアイテムをどのように見つけるのでしょうか?

4

2 に答える 2

5

ええと...上位の K 用語を見つけることは、実際には大きな問題ではありません。この分野の重要なアイデアの 1 つは、「ストリーム処理」のアイデアです。つまり、データの 1 回のパスで操作を実行し、ある程度の精度を犠牲にして確率論的な答えを得るというものです。したがって、次のようなデータ ストリームを取得するとします。

ABKACAABBCDFGABFHIBACF IUXAC

あなたが望むのは、上位の K 個のアイテムです。単純に、各アイテムのカウンターを維持し、最後に各アイテムのカウントでソートします。これにはO(U)スペースとO(max(U*log(U), N))時間がかかります。ここUで、 は一意のアイテムNの数であり、 はリスト内のアイテムの数です。

ケースUが小さい場合、これは実際には大きな問題ではありません。しかし、何十億、何兆ものユニークな検索を伴う検索ログの領域に入ると、容量の消費が問題になり始めます。

そこで、人々は「カウント スケッチ」のアイデアを思いつきました (詳細については、ウィキペディアのカウント ミニ スケッチ ページを参照してください)。ここでは、長さのハッシュ テーブル A を維持し、n各アイテムに対して 2 つのハッシュを作成します。

h1(x) = 0 ... n-1一様確率で

h2(x) = 0/1それぞれ確率 0.5

あなたはそうしますA[h1[x]] += h2[x]。重要な観察は、各値が +/-1 にランダムにハッシュされるためE[ A[h1[x]] * h2[x] ] = count(x)、Eは式の期待値であり、count は x がストリームに出現した回数です。

もちろん、このアプローチの問題は、各推定値に依然として大きな分散があることですが、ハッシュ カウンターの大きなセットを維持し、各セットから平均または最小カウントを取得することで対処できます。

このスケッチ データ構造を使用すると、各項目のおおよその頻度を取得できます。これで、これまでで最大の頻度推定値を持つ 10 項目のリストを維持するだけで、最後にリストが完成します。

于 2014-05-20T08:21:10.810 に答える
1

特定の民間企業がそれをどのように正確に行うかは一般に公開されていない可能性が高く、そのようなシステムの有効性を評価する方法は設計者の裁量に任されています (あなたであれ、Google であれ、誰であれ)。

しかし、ツールや研究の多くは、始めるためのものです。リアルタイムでのストリーミング データの処理を可能にする、Stormなどのトップレベルの Apache プロジェクトの多くを含む、いくつかのビッグ データ ツールを確認してください。

また、KDD やWSDMなどのビッグデータやウェブ サイエンスのカンファレンスや、Google Research が発表した論文もチェックしてください。

このようなシステムを設計する方法は難しく、正解はありませんが、開始するためのツールと調査が用意されています。

于 2014-05-17T14:15:41.193 に答える