快速可扩展的相似性检测

Question

我有一个包含文档的大型postgresql数据库。每个文档都表示为表中的一行。当新文档添加到数据库中时，我需要检查重复项。但我不能仅仅使用select来找到完全匹配的内容。两个文档可以略有不同，但仍然可以被视为重复的，例如，如果一些次要字段不同，而所有其他字段相同。

我研究了这个问题，并找到了解决这个问题的方法。可以为每个文档计算MinHash签名，并构建倒排索引，从数据库中查询相似的文档。但是我不能理解如何将MinHash映射到关系数据库。

据我所知，MinHash签名是N个散列的列表，其中N是一些属性。相似度计算如下：

# Given 2 signatures Sa and Sb containing N hashes.
# Calculate number of equal hashes Neq.
number_of_equal_hashes = 0
for ix in range(0, N):
    if Sa[ix] == Sb[ix]:
        number_of_equal_hashes += 1
similarity = float(number_of_equal_hashes)/N

如果您已经有两个签名，这很简单，问题是在数据库中找到相似度小于或等于某个值的所有文档(具有相应的签名)。

例如，我可以创建包含多个列的表，如下所示：

| minhash0 | minhash1 | minhash3 | docid |

每个minhash列对应于文档属性之一的minhashX，docid是文档的标识符。我可以这样查询相似的记录：

select * from invidx
where ((case when minhash0=minhash2search0 then 1 else 0 end) +
       (case when minhash1=minhash2search1 then 1 else 0 end) +
       (case when minhash2=minhash2search2 then 1 else 0 end))/N > THRESHOLD

其中minhash2searchX是新文档的最小散列，阈值是最小相似度。但是这种方法需要完整的扫描。有什么方法可以加速这个算法吗？

Answer 1

为了利用倒排索引的优势，我建议你使用全文搜索引擎，例如Lucene或Solr (基于Lucene)

您可以构造"document“(对于Lucene而言)，它将包含与您的文档(数据库记录)的MinHashes相关联的字段。请注意，您还可以对数值字段进行索引(您只需要在scheme中描述字段类型)。此外，您必须存储每个文档的主键，以将Lucene“文档”映射到数据库中的记录上。

为文档的整个集合建立索引。

为了找到与给定文档相似的文档，您必须为每个字段计算MinHashes，并为similar文档计算query Lucene：

field1:MinHash1 OR field2:MinHash2 OR ...

与文档匹配的字段越多，的排名就越高，的排名就越高。因此，如果它们在您的案例中确实相似，那么您可以选择几个排名最高的文档，然后做出决定

此外，字段的boosting可能对您很有用

Answer 2

您的哈希表应该包含两列：

| minhash | docid |

它应该在minhash上建立索引。

当一个新文档到达时，您依次搜索它的每个minhash，查询表以查找共享该minhash的先前文档。您建立了这些先前文档共享了多少minhashes的计数，然后丢弃了共享的minhashes少于(例如) 50%的所有minhashes。这有效地产生了至少(估计) 50%相似的所有文档的集合。

最后，为每个新文档的minhashes插入新行。

使用Lucene或Solr的是一个糟糕的解决方案。它将需要更多的存储空间，实现起来会更复杂，效率也会大大降低。是的，您可以让Lucene为您的minhashes建立索引，并按照stemm的建议运行查询。这将返回共享单个minhash的每个文档，根据您的数据大小，minhash可能是数万或数十万。然后，您必须使用“相似性”功能将其中的每一个与您的传入文档逐一进行比较，这将非常慢。

Lucene确实提供了一个"MoreLikeThis“功能来查找共享某些关键字的文档，但这将遗漏许多类似的文档，而minhash方法将会找到这些文档。