Googleトレンドのシステム設計？

Question

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

課題：

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

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

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

これは私の仮定があるものです（私はMapReduceの/ NoSQLの技術のゼロpractial経験を持っている）

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

としてだけでなく、タイムスタンプによって検索のリストを維持し、検索の範囲、カテゴリなど

例：

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

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

質問：Kurt Cobain用語の検索

• 検索用語の頻度を効率的にどのように計算するのですか？

• つまり、大きなデータセットがある場合、上位10個の頻繁なアイテムはどのようにして分散スケール可能な方法で見つけられますか？

  特定の民間企業が、それは一般に公開そうではなく、どのようなシステムの有効性を評価するためには、設計者の裁量でどのように正確に

Answer 1

を始めるために用意されてい...トップのK項を見つけることは本当に大きな問題ではありません。この分野の重要なアイデアの1つは、「ストリーム処理」、すなわちデータの単一パスで操作を実行し、ある確率を犠牲にして確率的な答えを得るという考えである。このように、あなたは次のようなデータのストリームを取得すると仮定します。あなたが望む

A B K A C A B B C D F G A B F H I B A C F I U X A C

はトップKアイテムです。純粋に、各アイテムのカウンタを維持し、最後に各アイテムのカウントをソートします。これにはO(U)スペースとO(max(U*log(U), N))時間がかかります。Uはユニークアイテムの数で、Nはリスト内のアイテムの数です。

Uが小さい場合、これは実際には大きな問題ではありません。しかし、検索ログの領域に数十億回のユニークな検索が行われると、スペース消費量が問題になり始めます。

だから、人々は「カウントスケッチ」というアイデアを思いつきました（ここではさらに読むことができます：count min sketch page on wikipedia）。ここでは、長さnのハッシュテーブルAを維持し、各項目について2つのハッシュを作成します。

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

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

であなたは、その後A[h1[x]] += h2[x]を行います。重要なのは、各値が+/- 1にランダムにハッシュするため、です。ここで、Eは式の期待値で、countはストリームに現れた回数です。

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

このスケッチデータ構造では、各項目のおおよその頻度を得ることができます。さて、あなたは今まで最大の頻度の推定値を持つ10項目のリストを維持し、最後にあなたのリストを保有します。

Answer 2

（それはあなたやGoogleや誰も）

しかし、ツールや研究の多くは、あなたを始めるためにそこにあります。 StormのようなトップレベルApacheプロジェクトの多くを含むビッグデータツールをチェックしてください。

Big Data and Web ScienceカンファレンスKDDのようなまたはWSDM、だけでなく、論文は、このようなシステムを設計するためにどのようにGoogleの研究によって

を出してはいない正解と挑戦ですが、ツール、および研究は、あなたがよく