具体来说：给定两个对象，我可以将它们的不相似性计算为一个数字，即度量 - 更高的值意味着更少的相似性，0意味着对象具有相同的内容。计算此数字的成本与较小对象的大小成比例（每个对象都有特定大小）。
我需要快速查找与某个对象相似的对象集。
具体来说：我需要生成一个数据结构，将任何对象o映射到与o不相似度超过d的对象集，其中d是某个不相似度值，列出集合中的对象所需的时间不超过数组或链接列表中的时间（也许它们实际上就是）。通常，集合将远小于对象总数，因此执行此计算真正值得。如果数据结构假设固定的d，那么它已经足够好了，但如果它适用于任意d，那就更好了。
您以前见过这个问题或类似的问题吗？有什么好的解决方案吗？
具体来说：一种直接的解决方案涉及计算所有对象对之间的不相似度，但这很慢 - O(n2)，其中n是对象数量。是否有更低复杂度的通用解决方案？
我认为解决方案取决于更多关于您问题性质的详细信息。
你需要多次查找相似的对象，还是只需要一次？如果需要多次，那么创建一个数据结构，在每对对象之间计算差异一次，然后将对象连接到相似的对象，以便可以快速检索列表而无需重新计算，这可能是非常有用的性能增强。
计算的性质是什么？在极端情况下，如果差异的性质是例如两个人之间的身高差异，那么通过按身高排序维护列表将让您非常快速地找到相似的对象。我假设实际问题比这更复杂，但是遵循这种逻辑，如果差异是几个线性量的总和，则可以创建一个多维数组，然后在概念上将相似对象集合想象为围绕参考对象的n维球体（即圆形、球体、超球体等），并直接找到它们。实际上，我想到了一个方法，如果半径计算过于复杂或运行时间太长，一个好的近似值是在参考对象周围创建一个n维立方体（即正方形、立方体、四维立方体等），检索所有位于该立方体内的对象作为“候选对象”，然后只对候选对象进行实际计算。
for (x1=o.a1-d;x1<o.a1+d;++x1)
{
for (x2=o.a2-d;x1<o.a2+d;++x2)
{
for (x3=o.a3-d;x1<o.a3+d;++x3)
{
if (array[x1][x2][x3]!=null
&& (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
{
... found a match ...
}
}
}
}
我怀疑差异规则比那更复杂，但没关系，只需增加算法的复杂性以匹配规则的复杂性。重点是使用数组来限制您必须检查的对象集。
对象示例： 图像，文档。当然，使用这些对象的原始表示通常是没有用的。通常，人们会对原始形式进行预处理，并将其转换为某种规范化形式（例如对于文档，可以使用向量表示，其中每个条目表示某个单词出现的次数/百分比，对于图像，则可以是表示在图像中找到的视觉特征）。
如果d是固定的，n^2的预计算是可行的，你可以使用一个链表来表示每个对象的图形表示。 您可以使用近似最近邻算法获得更高效的解决方案，但代价是准确性。
similarity(a,c) = similarity(a,b) op similarity(b,c)
其中op是二元运算符，例如乘法或加法。
没有更多度量细节，很难说。我没有任何关于消除O(n^2)方面的想法，但可能有一种方法可以减少涉及的某些常数。例如，如果您拥有欧几里得度量d(p,q) = sqrt( (p_1-q_1)^2 + ..+ (p_n-q_n)^2)，则可以将距离d平方并将其与(p_i-q_i)^2的部分和进行比较，在超过d^2时停止。
这是否会真正为您节省时间取决于比较的成本与仅计算求和项以及通过执行此操作可以避免多少个求和计算（显然，d越小，越好）。
不能使用 kd-tree 吗？
如果可能的话，可能需要对维度进行归一化。之后，您只需要填充树，使用“最近的 N 个邻居”搜索，并尝试在某个范围内找到任何对象。
我们可以假设相似性是可传递的，即 diff(a,c) == diff(a,b) + diff(b,c) 吗？如果是这样，您可以尝试以下方法：
o 相似度为 s 的对象，请在排序列表中查找 o，并向左和向右搜索，直到差异增大到大于 s 为止。这样做的好处是可以一次性完成排序，并且随后的集合构建与将在集合中的成员数量成比例。