問題タブ [hyperloglog]

私が対処しようとしている問題は些細なことのようです。イベントの膨大なコレクションがあります（実際にはモバイルアプリからのものなので、モバイルイベントです）。各イベントは、いくつかの属性によって記述されます。

これらのイベントを hdfs に保存しています。解決しようとしている問題は、ユーザーがこれらのイベントをほぼリアルタイムで分析できるようにすることです。分析とは、特定の列、興味深い日付範囲のみを選択し、さまざまな電話モデルから発生したイベントの数を確認できることを意味します. たとえば、次のデータセットがあるとします。

また、ユーザーが 2015 年 7 月からのさまざまな電話からのイベントの数を知りたいと仮定します。彼が探している答えは次のようになります。

イベントの数が膨大なので、集計を計算して cassandra に保存しようとしました。集計は 1 日ごとに計算され、前の例のデータセットを使用すると、集計は次のようになります。

問題は、それらがまだ多すぎることです。要求された日付範囲から集計を合計するためにオンデマンド タスクを実行するには、まだ Spark が必要です。遅く、多くのネットワーク転送が必要です。HyperLogLog やその他の同様のアルゴリズムについてよく読んでいますが、ここでそれらをどのように使用できるかわかりません。正確な結果はあまり気にしません。見積もりは私にとってはかなり良いです。誰かが私にできることを提案できますか?

0 から 100,000 までの値の大きなリストがあります (わかりやすくするために、ここでは文字で表しています)。各入力には数千の項目がある場合があります。

特定のしきい値を超える数の数を見つけたい。たとえば、しきい値が 3 の場合、答えは{a: 4, b: 5}です。

これを行うための明白な方法は、ID でグループ化し、各グループをカウントしてからフィルター処理することです。

これは言語にとらわれない質問ですが、Clojure では (Clojure を知らなくても気にしないでください!):

この関数は、非常に多数の入力に対して実行されます。各入力は非常に大きいため、グループ化とフィルタリングはコストのかかる操作です。入力が特定のしきい値を超える出力を生成できない場合、または問題空間を分割できない場合に、早期に返されるある種のガード関数を見つけたいと考えています。たとえば、最も単純なのはif the size of the input is less than the size of the threshold return nil.

入力が出力を生成できない場合に計算をスキップする、より優れたガード関数を探しています。または、出力を生成するより迅速な方法。

明らかに、グループ化自体よりも安価でなければなりません。優れた解決策の 1 つは、個別の入力セットによる入力のカウントに関係していましたが、最終的にはグループ化と同じくらいコストがかかりました...

確率的なデータ構造が鍵を握る可能性があるという考えがあります。何か案は？

(hyerloglog をタグ付けしましたが、カウントが提供されないため該当しないと思います)

Hyperloglog がどのように機能するかは知っていますが、Hyperloglog が実際に適用されるのはどのような状況か、つまり、Hyperloglog を使用する意味とその理由を理解したいですか? 実際の問題を解決するために使用したことがある場合は、共有してください。私が探しているのは、Hyperloglog の標準エラーを考えると、実際にどのアプリケーションで実際に使用されているのか、そしてなぜそれが機能するのかということです。

さまざまな企業が、「いいね」/「ビュー」/「リツイート」などの数をカウント/インクリメントする方法、または同様のものを大規模に解決する方法について、いくつかの洞察を得たいと思います。

月間アクティブ ユーザーが 5,000 万人を超えるユーザーベースでは、Redis と Cassandra の両方が userId のセットを格納して、セットのカーディナリティ (たとえば、ビューアーの数) をすばやく取得するために使用されているのを見てきました。これらのソリューションには欠点がありますが、うまく機能し、スケールアウトできます。ただ、この場合、他のお店は何を使っているのか気になります。

具体的には、次のソリューションを実行します。

• セット、またはその他のデータ構造を使用しますか、それとも単純なキーと値だけを使用しますか?
• 正確な数か、おおよその数か?
• インメモリのみですか、それともハイブリッドですか?
• オープンソース ソリューションですか、それとも自家製ですか?
• その上にハイパーログログの推定を備えた軽量のセットのみのストレージシステムを構築した人はいますか?

確率的平均を使用してハイパーログ ログ カウント アルゴリズムを実装しようとしています。そのためには、さまざまなサブストリーム内のアイテムをハッシュするために、多くの独立したユニバーサル ハッシュ関数が必要です。

hashlibで利用できるハッシュ関数はごくわずかで 、シードなどを提供する方法はないようです。サブストリームごとに異なるソルトを使用することを考えています。

私たちは現在、興味深い問題に直面しています。すべてのアイテムを保存する必要なく、セットのカーディナリティを推定したいと考えています (通常、ビットマップ/ビットセットは優れたアプローチです)。非常に優れたアルゴリズムは、いわゆる HyperLogLog ランダム化アルゴリズムです (詳細については、 http://antirez.com/news/75 を参照してください)。

ここでの問題は、セットをUNIONとしてのみマージできるため、基本的にはORの組み合わせです。

実際には、セットを OR だけでなく AND と組み合わせたいと考えています。これらの操作を組み合わせたいとさえ思っています。

例: set1 AND (set2 OR set3) OR (set4 AND set5)

各セットには、数百万の範囲のカーディナリティがある場合があります。各値のサイズは 128 ビットです。

各セットは、「HLL、ブルーム フィルター、単純なリスト、またはこれらの組み合わせ」など、任意の方法で表すことができます。アルゴリズムは、実行可能なスペースを使用して、可能な限り短い時間で実行する必要があります。

何か案は？