最近邻搜索与近重复检测

Question

我在寻找一些AI/ML和非AI/ML解决方案的“近重复检测”问题(文本，图像，音频)，我发现有一个类似/准确的问题，即“最近邻居搜索”，也似乎处理方式与“接近重复检测”。我不知道这两个问题之间是否有任何差异，或它们的解决办法有什么不同。

Answer 1

从英语的角度看，这两个问题的名字在语义上似乎是一样的。

在最近邻搜索中，您有一组元素，给定一个引用元素，您希望在集合中搜索一个元素，该元素相对于给定的度量而言是最接近引用的元素。

在几乎重复的检测中，您有一组元素，给定一个引用元素，您希望在集合中搜索一个元素，该元素是相对于给定度量的引用的最接近的副本。

话虽如此，在文学作品中，当集合中的元素是文本文档时，我看到人们通常使用后面的名称。在这种情况下，一个示例算法包括获取文本文档( k-shingles )大小为k的一组窗口，并使用Jaccard度量(两个文档中共有的瓦数除以不同标记的数目)在每个文档的k-标记集之间进行比较。为了避免显式地计算Jaccard度量，有一个定理。如果你将所有的k-条散列成64位整数(例如)，并考虑从64位整数到64位整数的随机排列，那么，如果将置换应用到每个文档的散列k-条集合，那么两组置换值中每一组最小元素相等的概率等于两个文档之间的Jaccard度量。

另一方面，如果元素集是R^n的子集(例如)，我看到人们通常使用名字。在这种情况下，存在许多技术。例如，一些有用的数据结构是八叉树，kd-树.

尽管如此，人们也使用矢量化技术将一些元素集合转换为R^n的子集，例如signal2vec、word2vec等。