快速相似性检测

我有大量的对象，我需要找出它们之间的相似之处。

确切地说：给定两个对象，我可以将它们的差异计算为数字，ametric http://en.wikipedia.org/wiki/Metric_%28mathematics%29- 值越高意味着相似度越低，0 意味着对象具有相同的内容。计算该数字的成本与较小对象的大小成正比（每个对象都有给定的大小）。

我需要能够在给定一个对象的情况下快速找到与其相似的一组对象。

确切地说：对于某些相异值 d，我需要生成一个数据结构，将任何对象 o 映射到与 o 不相似的对象集，这样列出集合中的对象所花费的时间不会比它们花费的时间多。位于数组或链表中（也许它们实际上是）。通常，该集合将比对象总数小得多，因此执行此计算确实值得。如果数据结构假设一个固定的 d 就足够了，但如果它适用于任意 d，那就更好了。

您以前见过这个问题或类似的问题吗？什么是好的解决方案？

To be exact: a straightforward solution involves computing the dissimilarities between all pairs of objects, but this is slow - O(n²) where n is the number of objects. Is there a general solution with lower complexity?

我需要生成一个数据结构 将任何对象 o 映射到集合 物体与 o 的相似度不超过 d，对于某些相异值d。

当小计变得大于时，放弃相似性计算可能是最快的d。例如，如果您的相似性基于余弦或豪斯多夫距离，则可以轻松完成。

PS: 如果无法做到这一点，则您的问题可能与 k 最近邻问题（或更准确地说是具有阈值邻域的最近邻问题）有关。您应该寻找无需计算所有距离即可找到附近成员的算法（可能使用三角不等式）。维基百科应该帮助您探索合适的算法。