16

我一直在处理一些非常大的数据集，通常是数十亿个元素，它们都维护在memcached云中并定期转储到文件中，对于我的一项任务，我正在尝试计算基数这一套。

在某些情况下，每个项目都包含一个 IP 和一些其他属性来识别一个人，并以 base64 编码，项目大小为 20 字节。通过删除某些字段来减小项目的大小是不可能的。

这是将我的数据集模拟为内存版本的东西（感谢this post for string generation）：

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 方式，而是想探索算法在单台机器上有效地做到这一点，因为这可以应用于其他几个不同的项目。

4

2 回答 2

8

我建议使用 Hash Sketches，即（Super）Log Log 草图或 Hyper Log Sketches。

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

于 2012-04-15T20:03:04.917 回答
3

我建议您尝试使用布隆过滤器。即使有如此大量的数据，您也可以在适度的系统要求下实现极低的错误率。鉴于您将使用（大致）最佳 k=ln(2)*(bloom filter size in bits)/(10billions)，您可以计算您的bloom filter size in bits as -((10billions)*ln(desired false positive率))/ln(2)^2。

例如，使用少于 2gigs 的内存，您可以获得 0.1% 的错误率。所有这一切的一个非常快速且极其简单的实现是http://mike.axiak.net/python-bloom-filter/docs/html/

于 2012-04-15T20:12:47.110 回答