私は非常に大きなデータセット（通常は数十億の要素）を使用して作業を行っています。これらはすべてmemcachedクラウドに保持され、定期的にファイルにダンプされます。私のタスクの1つとして、カーディナリティをカウントしようとしています。このセット。
コンテキストによっては、各アイテムにIPと、個人を識別するその他の属性が含まれ、base64でエンコードされます。アイテムのサイズは20バイトです。一部のフィールドを削除してアイテムのサイズを縮小することはできません。
これが私のデータセットをメモリ内バージョンとしてエミュレートするものです（文字列生成のためのこの投稿に感謝します）：
import base64, os
dataset_size = 10000000000 # that's 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]
私の最初のアプローチは、次のようなハッシュセットを使用することでした。
uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)
これは理論的には小さなデータセットでは問題なく機能しますが、問題があると推測できます。
- 私は自分のデータの独自性を推測することはできません。データセットの50％を一意にすることも、100％にすることもできます。これは一定の時間間隔で動的に生成され、多くの要因（たとえば時刻）によって異なります。
- 100億のデータセットサイズ。Base 64でエンコードされた各アイテムは20バイトで、100億倍は平均して数百ギガバイトです。残念ながら、私はそれほど多くのRAMを搭載したマシンにアクセスできません！
私は宿題をして、せいぜいいくつかの研究論文、またはいくつかのあいまいな図書館を見つけましたが、これの目標の一部は、どのアプローチが機能し、その理由を理解することです。
だから私はあなたにPythonユーザーを呼んでいます、あなたは私がカーディナリティを効率的に推定するのを助けるであろうアルゴリズムを知っていますか？複雑さというのは、実行時間の複雑さについてはそれほど気にしないということですが、スペースの複雑さについてはもっと焦点を合わせています。パフォーマンスが大幅に向上する場合は、精度を少し犠牲にしてもかまいません（したがって、それが理想的であっても、一意の正確な数を知る必要はありませんが、おそらく実行可能なアプローチではありません）。5％までは許容できると思います。このプロジェクトのためにPythonで具体的に何かを探しています。
あなたが提供できるどんな助けにも感謝します！
一部の人が指摘したように、私はHadoop / MRを使用できますが、この特定のプロジェクトでは、MRの方法を採用したくありません。これは、単一のマシンで効率的にこれを行うためのアルゴリズムを検討したいと思います。他のいくつかの異なるプロジェクト。