問題タブ [hyperloglog]

LogLogアルゴリズムの有効な実装はどこにありますか？自分で実装しようとしましたが、私のドラフト実装では奇妙な結果が得られます。

ここにあります：

理由は不明ですが、実装はmax_errorパラメータに非常に敏感であり、結果の大きさを決定する主な要因です。確かに、いくつかの愚かな間違いがあります:)

更新：この問題は、新しいバージョンのアルゴリズムで解決されています。その実装については後で投稿します。

私は最近、空き時間にさまざまなアルゴリズムについて学んでおり、非常に興味深いと思われるアルゴリズムに出くわしたのは、HyperLogLog アルゴリズムと呼ばれるもので、リスト内の一意のアイテムの数を推定します。

「カーディナリティ」の値 (これは最近まで、計算されたものであり、推定されたものではないと常に想定していました) を見たときに、MySQL の時代に戻ったので、これは特に興味深いものでした。

だから私は、配列内の一意のアイテムの数を計算するアルゴリズムをO ( n )に記述する方法を知っています。私はこれをJavaScriptで書きました：

しかし、問題は、私のアルゴリズムがO ( n ) であるのに対し、大量のメモリを使用する (値を に格納するTable) ことです。

O ( n ) 時間でリスト内の重複をカウントし、最小限のメモリを使用する方法について、この論文を読んでいます。

ビットまたは何かをハッシュしてカウントすることにより、特定の確率（リストが均等に分散されていると仮定）内でリスト内の一意のアイテムの数を推定できることを説明しています。

論文を読んだのですが、理解できないようです。誰かがより素人の説明をすることができますか？ハッシュとは何かは知っていますが、この HyperLogLog アルゴリズムでハッシュがどのように使用されているかわかりません。

Flajolet et alによるHyperLogLog アルゴリズムは、ごく少量のメモリを使用してセットのカーディナリティを推定する巧妙な方法を説明しています。ただし、計算では元のセットのN個の要素すべてが考慮されます。元のNの小さなランダムサンプル（たとえば、10％）にしかアクセスできなかった場合はどうなりますか？HyperLogLogまたは同様のアルゴリズムをこの状況にどのように適応させることができるかについての研究はありますか？

これは本質的に、明確な価値の推定として説明されている問題であり、豊富な研究が存在することを認識しています（概要については、たとえばこの論文を参照してください）。ただし、私が知っている明確な値の推定に関する調査では、HyperLogLogで使用されているアプローチとは非常に異なる多くのアドホック推定量を使用しています。したがって、誰かがHyperLogLogを明確な値の見積もりの​​問題に適応させることをすでに考えているのではないかと思います。

HLL を使用したセットのカーディナリティのカウントを時系列分析に使用する方法について、誰かが説明したり、説明にリンクしたりできますか?

druid.ioがまさにこれを行うと確信していますが、特定のライブラリ/データベースまたは特定の HLL 実装なしで、HLL のみでこれを行う方法の一般的な説明を探しています。

これを行う単純な方法は、カウントするものにタイムスタンプをプレフィックスすることです。たとえば、1000001 秒から 1000060 秒までのイベントをカウントする場合、redis HLL API を例として使用します。

これが持つ問題の 1 つに過ぎません。たとえば、最後の 1 分間の特定のイベントの数を調べるために、特定の範囲内の各秒を反復処理する必要があるということです。

Redis は最近、HyperLogLog と呼ばれる新しいデータ構造をリリースしました。これにより、一意のオブジェクトの数を保持でき、12k バイトのサイズしか占有しません。私が理解していないのは、Redis の PFCOUNT コマンドが技術的には書き込みコマンドと言われていることです。これはなぜですか？

注: この関数を呼び出すことの副作用として、HyperLogLog が変更される可能性があります。これは、最後の 8 バイトがキャッシュ目的で最新の計算されたカーディナリティをエンコードするためです。したがって、PFCOUNT は技術的には書き込みコマンドです。

の独自の実装を作成しHyperLogLog algorithmました。これはうまく機能しますが、多くの (約 10k ～ 100k) の HLL 構造を取得してマージする必要がある場合があります。

それぞれをビット文字列として保存するため、最初に各ビット文字列をバケットに変換する必要があります。HLLがたくさんあるので、私が望むよりも時間がかかります.

現在、実行時間の約 80% で、HLL ごとに次のコード行が 1 回呼び出されます。

my @buckets = map { oct '0b'.$_ } unpack('(a5)1024', $bitstring);

より速くする方法はありますか？

HyperLogLog の定義を後にすると、タスクは次のように説明できます: $bitstring1024 個の 5 ビット カウンターで構成されている場合 (したがって、各カウンターは最大 32 個の値を持つことができます)、1024 個の整数の配列に変換する必要があります。

PFADD コマンドに関する Redis のドキュメントによると:

次の2点について説明できる人はいますか？

1. これは、カウンタが実際に 1 インクリメントされた場合、PFADD が「1」を返すことを意味しますか? PFADD を実行した後、新しい PFCOUNT が になることが保証されていますPFCOUNT(before) + output of PFADDか? 言い換えれば、シングルスレッドのクライアントは、PFADD の出力のみを使用してカウントを追跡できますか?
2. PFADD が「0」または「1」を返す場合、それぞれ「キャッシュ ヒット」と「キャッシュ ミス」に変換されますか?