問題タブ [hyperloglog]

Unique Visitor についてレポートできるようにする必要がありますが、キーのすべての可能な順列を事前に計算して複数のテーブルを作成することは避けたいと考えています。

単純な例として、次の列を持つテーブルで月間ユニーク数を報告する必要があるとします。

• 日付 (月/年)
• page_id
• country_id
• device_type_id
• month_uniques

Druid と Redis では、Hyperloglog データ型がこれを処理し (わずかな誤差が許容できると仮定して)、ディメンションの任意の組み合わせでクエリを実行し、一意の実行可能な見積もりを受け取ることができます。

PostgreSQL の世界で見つけた最も近いプラグインは postgresql-hll プラグインですが、PostgreSQL 9.0 以降用のようです。

訪問者 ID を事前に計算したり保存したりすることなく、Redshift でこれを表す方法はありますか (テーブルのサイズを大幅に拡大しますが、RedShift の「概算カウント」hll 実装を使用できます)。

注: RedShift が推奨されるプラットフォームですが、CitusDB などの他の自己ホスト型 PostgreSQL フォークがこれをサポートできることは既に知っています。RedShift でこれを行う方法を探しています。

セットからの要素の削除をサポートする必要があることを考慮して、セットのカーディナリティを計算するための確率的アルゴリズムはありますか? 一部のセットとその結合のカーディナリティを計算するために HyperLogLogs を使用してきましたが、セットから要素を削除する必要が生じたとき、現在のソリューションは不適切になりました。おそらく、このトピックに関連する研究や論文がいくつかありますので、アドバイスをお願いします。

Algebird で Twitter の HyperLogLog の実装を使用しています。数値 N と、HyperLogLog を使用して徐々に増加するコレクションの現在のサイズを推定し、それが N より大きいか小さいかをテストするシステムのチェックが与えられた場合、このチェックをテストし、 HyperLogLog を呼び出すコードが正しければ、ほぼ確実に合格するのでしょうか? テスト対象のシステムは非決定論的です。その理由の 1 つは、マルチスレッドであるためです。

私が最初に考えたのは、このユース ケースで信頼できる統合テストを作成する正しい方法は、「標準を破棄する」ことであるということでした。では、HyperLogLog がアイテムの総数を N を超えると推定するためにエンドポイントにポストするのに十分なアイテム (M) の数は、たとえば >= 0.999999 の確率で?

または、より良いアプローチがありますか？

標準のエラー境界は設定可能ですが、それは、たまに目にする可能性のある最大のエラー境界を直接教えてくれるわけではありません - これは、マスター上でランダムに失敗した CI ビルドが時間と無駄の原因となるのを避けるために私が気にかけていることです。 -引っ張る！

また、テストで乱数データを生成する方法が、関連する点で一様分布の乱数データを生成しない可能性があり、確率計算に重大な影響を与える可能性があることも懸念しています.

次のようなサンプルドキュメントを含むMongoDBのコレクションがあります-

問題文

個別の数の IP をフェッチしながら、任意のフィールドをグループ化できるはずです。

集計クエリ -

望ましい結果が得られますが、遅いです。同様にip、別のものを使用してカウントするの$groupは遅いです。出力は -

私が試したこと

これにはHyperloglogの使用を検討しました。Redis 実装を使ってみました。データ全体をストリーミングして、グループ化したものだけを投影し、PFADDそれを対応する redis の hyperloglog 構造に変換しようとしました。

ロジックは次のようになります-

これを100万以上のデータポイントで実行しようとしました。ストリーミングされるデータのサイズは約 1GB で、Mongo と Node サーバー間の接続は 1 Gbps でした。このコードは十分に高速に実行されると予想していました。ただし、かなり遅かったです (MongoDB でのカウントよりも遅かった)。

私が考えたが実装しなかったもう 1 つのことは、各クラスのバケットを事前に作成し、流入するデータに合わせてリアルタイムでバケットをインクリメントすることでした。

私が間違っている可能性があること、またはここで改善できることを提案して、hyperloglog を最大限に活用できるようにします (私は Redis に制約されておらず、あらゆる実装にオープンです)。

ここで、PFADD 操作を使用して値をキーに挿入する単純なコードを実行しようとしていますが、次のエラーが発生します。

ResponseError: 不明なコマンド 'PFADD'

私のコードは次のとおりです。

• Python バージョン: 2
• パンダのバージョン: 0.19.0
• Redis バージョン: 2.10.5`

ここで何か不足していますか？