如何在大数据集中删除重复项

引言

处理大型数据集通常是令人畏惧的。由于计算资源有限，尤其是内存，即使是执行一些基本任务，例如计算不同元素的数量、成员资格检查、过滤重复元素、查找最小值、最大值、前 N 个元素，或者执行并集、交集、相似度等集合运算，都可能具有挑战性。

概率数据结构在这些情况下非常有用，因为它们可以极大地减少内存需求，同时仍能提供可接受的准确性。此外，由于查找（和添加）依赖于多个独立的哈希函数，可以并行化，因此您还可以获得时间效率。

我们广泛使用诸如 Bloom 过滤器、MinHash、Count-min sketch、HyperLogLog 等结构来解决各种问题。下面展示了一个相当直接的例子。

问题

我们为客户管理移动推送通知，我们需要防止的一种情况是，为同一个营销活动向同一个用户发送多个通知。推送通知是根据移动平台生成的推送通知令牌路由到各个设备/用户的。由于它们的大小（从 32 位到 4KB 不等），我们无法有效地索引推送令牌或将它们用作主要的用户密钥。

在某些移动平台上，当用户卸载然后重新安装同一个应用程序时，我们会丢失主要用户密钥，并为该设备创建一个新的用户配置文件。通常情况下，在这种情况下，移动平台会在重新安装时为该用户生成一个新的推送通知令牌。然而，这并非总是保证的。因此，在少数情况下，我们系统中可能会出现多个用户记录拥有相同的推送通知令牌。

因此，为了防止为同一个营销活动向同一个用户发送多个通知，我们需要从数亿到数十亿条记录的总数据集中过滤掉相对少量的重复推送令牌。为了让您有一个比例概念，仅仅过滤 1 亿个推送令牌所需的内存是 100M * 256 = 25 GB！

解决方案 – Bloom 过滤器

这个想法非常简单。

• 分配一个大小为 的位数组
• 选择 个独立的哈希函数 ，其范围是
• 对于每个数据元素，计算哈希并将位设置为“开”
• 对于成员资格查询 ，应用哈希并检查所有对应的位是否为“开”

请注意，由于哈希冲突，位可能被设置为“开”，导致误报，即可能报告一个不存在的元素存在，而目标是最小化这种情况。

关于哈希函数

Bloom 过滤器的哈希函数应该是独立的且均匀分布的。出于性能原因，MD5 或 SHA-1 等加密哈希不是好的选择。

一些合适的快速哈希函数包括 MurmurHash、FNV 哈希 和 Jenkins 哈希。

我们使用 MurmurHash –

• 它速度很快 – 比 MD5 快 10 倍
• 分布良好 – 通过卡方检验的均匀性
• 雪崩效应 – 对输入最微小的变化都很敏感
• 足够独立

Bloom 过滤器的尺寸

位数组的尺寸涉及选择最优的哈希函数数量来最小化误报率。

对于具有 位、 个哈希函数和 个元素的组合，误报概率，即当元素不存在时，所有对应的 位都被“开”的概率。

对于给定的 ，最小化 的最优 k 值

即，

因此，对于 1 亿个推送令牌，0.001 的错误概率

这比 25 GB 有了显著的改进。