我一直在工作中处理一些特别大的数据集，通常包含数十亿个元素，它们都存储在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)]
我的第一种方法是使用哈希集合，就像这样：
uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)
- 我不能假设我的数据是唯一的。我的数据集可能有50%是唯一的，也可能全部都是唯一的。这些数据是动态生成的，在规则时间间隔内变化，取决于许多因素（例如一天中的时间）。 - 数据集大小为100亿。每个项目以base64编码占用20个字节，乘以100亿大约是数百GB。不幸的是，我没有一台拥有那么多RAM的机器！
我已经做了功课，并找到了一些研究论文或一些晦涩的库，但部分目标是要理解哪种方法有效以及原因。
所以我向Python用户求助，您是否知道任何算法可以帮助我高效地估计基数？当我说复杂性时，我的意思是我并不太关心运行时间复杂度，而是更关注空间复杂度。如果能大大提高性能，我不介意牺牲一些准确性（所以我不一定需要知道唯一数的确切数字，即使这是理想的，但可能不是可行的方法）。对于这个项目，我正在寻找特别是使用Python实现的算法。
感谢您提供的任何帮助！
正如一些人指出的那样，我可以使用Hadoop/MR，但对于这个特定的项目，我们不想走MR的路线，而是想探索在一个单独的机器上高效完成此操作的算法，因为这可能适用于其他几个不同的项目。