在给定的位串数组(所有长度相同)和查询字符串Q中，找到与k最相似的top-k个字符串，其中字符串A和B之间的相似性定义为A和B中的数字1(运算并按位应用) 。
我认为这个问题应该有一个经典的结果。
k很小，只有几百个，而向量的数量则是数亿个，向量的长度是512或1024
最佳答案
解决此问题的一种方法是构造具有Russell-Rao相似度函数的K-Nearest Neighbor Graph (K-NNG)(有向图)。
注意，有效的K-NNG构造仍然是一个 Unresolved 问题，解决该问题的已知解决方案都不是通用，有效和可伸缩的。
您的距离函数通常称为Russell-Rao相似度(例如参见Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures - Dong, Charikar, Li 2011])。请注意，Russell-Rao相似度不是A Survey of Binary Similarity and Distance Measures - Choi, Cha, Tappert 2010(请参见metric):“d(x，y)= 0 iff x == y”的“if”部分为假。
在Properties of Binary Vector Dissimilarity Measures - Zhang, Srihari 2003中，作者提出了一种快速的分层搜索算法，该算法使用二进制向量空间中的非度量测度来查找k-NN。他们使用参数二进制矢量距离函数D(β)。当β= 0时，此函数简化为Russell-Rao距离函数。我不会称其为“经典结果”，但这是我所能找到的唯一一篇探讨这一问题的论文。
您可能要检查以下两个调查:A Fast Algorithm for Finding k-Nearest Neighbors with Non-metric Dissimilarity - Zhang, Srihari 2002和On nonmetric similarity search problems in complex domains - Skopal, Bustos 2011。也许您会发现我想念的东西。