如何在Python中有效地计算非常大的数据集的基数？

Question

我一直在玩一些非常庞大的数据集,通常是数十亿个元素,这些数据都保存在memcached云中并定期转储到文件中,对于我的一个任务,我正在尝试计算基数的基数.这一套.

对于某些上下文,每个项目包含一个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)]

我的第一种方法是使用这样的hashset:

uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)

虽然这在理论上适用于小型数据集,但您可以猜测有一个打嗝:

• 我无法对数据的唯一性做出任何假设.我可以拥有50%的独特数据集,或者我也可以拥有100%的数据集.这是以固定的时间间隔动态生成的,并且根据很多因素(例如,时间)而变化
• 数据集规模在10亿.以base 64编码的每个项目是20个字节,100亿次是平均几百GB.不幸的是,我无法访问具有那么多RAM的机器!

我完成了我的家庭作业,并发现了一些研究论文或一些不起眼的图书馆,但这部分目标的一部分是了解哪种方法有效以及为什么.

所以我打电话给你的Python用户,你知道任何能帮我估算基数的算法吗？复杂性我的意思是我并不关心运行时复杂性,但我更关注空间复杂性.我不介意牺牲一点准确性,如果它极大地提高性能(所以我不一定需要知道uniques的确切数量,即使这是理想的,但可能不是一个可行的方法).我会说高达5%是可以接受的.我正在为这个项目寻找专门用于Python的东西.

感谢您的任何帮助,您可以提供 !

正如一些人所指出的,我可以使用Hadoop/MR,但对于这个特定的项目,我们不想采用MR方式,并且希望探索算法在一台机器上有效地执行此操作,因为这可以应用于其他几个不同的项目.

Answer 1

我建议使用Hash Sketches,即(超级)Log Log草图或Hyper Log Sketches.

您可以检查并使用和改进我所做的简单python实现:https: //github.com/goncalvesnelson/Log-Log-Sketch