数据流中的近似重复检测

Question

我目前正在开发一个能生成大量文本内容的流式API。不出所料，API提供了大量重复数据，我们也有过滤接近重复数据的业务需求。

我对数据流中的重复检测做了一些研究，并阅读了有关Stable Bloom Filters的内容。稳定布隆过滤器是用于数据流中的重复检测的数据结构，具有错误阳性率的上限。

但是，我想要识别近似重复项，我还查看了散列算法，如LSH和MinHash，它们用于最近邻问题和近似重复检测。

我有点卡住了，正在寻找如何继续进行的指针，以及我可以查看的论文/实现？

Answer 1

1. 首先，将文本规范化为所有小写(或大写)字符，用空格替换所有非字母，将所有多个空格压缩为一个，删除前导空格和尾随空格；为了提高速度，我会在一次文本传递中执行所有这些操作。接下来，获取结果字符串的MD5散列(或更快的值)。在数据库中查找表中的MD5散列(作为两个64位整数)，如果存在，则是完全重复的，如果不存在，则将其添加到表中，并继续下一步。你会希望根据时间或内存使用来淘汰旧的散列。
2. 要查找需要转换为潜在签名(子串的散列)的规范化字符串的近似重复项，请参阅Greg Linden的SpotSigs论文和blog post。假设例程Sigs()对给定的字符串执行此操作，即给定规范化字符串x，Sigs(x)将返回一个小的(1-5) 64位整数集。您可以使用类似于SpotSigs算法的方法来选择签名文本中的子字符串，但是如果您对数据有所了解，使用自己的选择方法可能会执行得更好。您可能还想查看simhash算法(代码是here).
3. Given the Sigs()，有效地找到近似重复项的问题通常称为set similarity joins问题。SpotSigs的论文概述了一些启发式方法，以减少需要与新集合进行比较的集合数量，simhash方法也是如此。

Answer 2

http://micvog.com/2013/09/08/storm-first-story-detection/有一些很好的实现说明