1

この問題は、リザーバー サンプリングによって解決される問題と少し似ていますが、同じではありません。それもかなり興味深い問題だと思います。

大規模なデータセット (通常は数億の要素) があり、このデータセット内の一意の要素の数を推定したいと考えています。典型的なデータセットには、数個から数百万個の一意の要素が存在する場合があります。

もちろん、明らかな解決策は、遭遇した要素の実行中のハッシュセットを維持し、最後にそれらをカウントすることです。これにより、正確な結果が得られますが、全体をスキャンするときに潜在的に大量の状態を運ぶ必要があります。データセット (つまり、これまでに検出されたすべての一意の要素)。

残念ながら、私の状況では、これは私が利用できるよりも多くの RAM を必要とします (データセットが利用可能な RAM よりもはるかに大きい可能性はありません)。

スキャン中に比較的少量の状態を維持しながら、データセットを 1 回通過して最後に一意の要素数を推定できるようにする統計的アプローチがあるかどうか疑問に思っています。データセット。

アルゴリズムへの入力はデータセット (Java の用語では反復子) であり、推定された一意のオブジェクト数 (おそらく浮動小数点数) を返します。これらのオブジェクトはハッシュできる (つまり、必要に応じて HashSet に入れることができる) と見なされます。通常、それらは文字列または数値になります。

4

3 に答える 3

4

妥当な下限にブルーム フィルターを使用できます。データをパスして、セットに含まれていないアイテムをカウントして挿入するだけです。

于 2009-12-30T16:33:08.673 に答える
2

この問題は文献で十分に扱われています。さまざまなアプローチの優れたレビューはhttp://www.edbt.org/Proceedings/2008-Nantes/papers/p618-Metwally.pdfです。最も単純な (そして非常に高い精度が必要な場合に最もコンパクトな) アプローチは、リニア カウントと呼ばれます。ブルーム フィルターと同じように要素をビットベクター内の位置にハッシュしますが (1 つのハッシュ関数のみが必要であることを除いて)、最後に式 D = -total_bits * ln(unset_bits/total_bits) によって個別の要素の数を推定します。 . 詳細は紙面にて。

于 2012-03-14T00:40:04.217 に答える
1

信頼できるハッシュ関数がある場合は、正確なソリューションの場合と同じようにハッシュセットを維持できますが、ハッシュ値が小さな範囲外にあるアイテムは破棄できます。たとえば、32 ビットのハッシュを使用しますが、ハッシュの最初の 2 ビットが 0 であるアイテムのみを保持します。次に、最後に適切な係数を掛けて、一意の要素の総数を概算します。

于 2009-12-30T16:35:15.493 に答える