解决这个问题的一种方法是构建K 最近邻图 (K-NNG)使用 Russell-Rao 相似函数
\n\n请注意，高效的 K-NNG 构建仍然是一个悬而未决的问题，并且该问题的已知解决方案都不是通用的、高效的和可扩展的[引用自通用相似性度量的高效 K-近邻图构建 - Dong, Charikar, Li 2011]。
\n\n您的距离函数通常称为 Russell-Rao 相似度（例如，参见二元相似度和距离测量的调查 - Choi, Cha, Tappert 2010）。请注意，Russell-Rao 相似性不是度量（请参阅二元向量相异性度量的属性 - Zhuang, Srihari 2003）： “ d(x, y) = 0 iff x == y ”的“ if ”部分为 false。
\n\n在《A Fast Algorithm for Find k-Nearest Neighbors with Non-metric Dissimilarity》（A Fast Algorithm for Find k-Nearest Neighbors with Non-metric Dissimilarity）（Zhang, Srihari 2002）中，作者提出了一种快速分层搜索算法，用于在二元向量空间中使用非度量度量来查找 k-NN。他们使用参数二元向量距离函数 D(\xce\xb2)。当\xce\xb2=0时，该函数简化为Russell-Rao距离函数。我不会称其为“经典结果”，但这是我能找到的唯一一篇研究这个问题的论文。
\n\n您可能需要检查这两项调查：关于复杂领域中的非度量相似性搜索问题 - Skopal, Bustos 2011和最近邻搜索方法调查 - Reza, Ghahremani, Naderi 2014。也许你会发现我错过的东西。
\n