k查询位串
给定位串（所有长度相同）和查询字符串Q的排列找到与Q最相似的字符串，其中字符串A和B之间的相似性被定义为A和B中的数字1（操作并按位应用） 。
我认为这个问题应该有一个经典的结果。
k很小，数百个，而数亿的向量数和向量长度是512或1024
解决这个问题的一种方法是构造具有Russell-Rao相似度函数的K-最近邻图（K-NNG）（有向图）。
请注意，有效的K-NNG构造仍然是一个开放的问题，并且这个问题的已知解决方案中没有一个是通用的，高效的和可扩展的[引自通用相似性度量的高效K-最近邻图构造 - Dong，Charikar，Li 2011] 。
您的距离函数通常称为Russell-Rao相似性（例如，参见二元相似性和距离测量的调查 - Choi，Cha，Tappert 2010）。 请注意，Russell-Rao相似度不是度量标准（参见二元向量相异性度量的属性 - Zhang，Srihari 2003）：“d（x，y）= 0 iff x == y”的“if”部分为假。
在一个用非度量相异度查找k-最近邻居的快速算法中 - Zhang，Srihari 2002，作者提出了一种在二进制向量空间中使用非度量度量来发现k-NN的快速分层搜索算法。 他们使用参数二值矢量距离函数D（β）。 当β= 0时，该函数减少到Russell-Rao距离函数。 我不会把它称为“经典结果”，但这是我能找到的唯一一篇考察这个问题的论文。
您可能想要检查这两个调查：复杂领域的非度量相似性搜索问题 - Skopal，Bustos 2011和最近邻搜索方法调查 - Reza，Ghahremani，Naderi 2014.也许你会发现我错过的东西。
这个问题可以通过编写简单的Map和Reduce作业来解决。 我既不声称这是最好的解决方案，也不声称这是唯一的解决方案。
另外，你在评论中已经公开了k是几百个，有几百万个比特串，而且它们的大小都是512或1024。
映射器伪代码：
现在，组合器可以合并来自每个具有相同相似性的映射器的所有bitStrings列表。
Reducer伪代码：
从reducer的输出中，您可以提取top-k位串。
因此，MapReduce范例可能是您正在寻找的经典解决方案。
链接地址: http://www.djcxy.com/p/92083.html下一篇: How to merge multiple (npm) package.json files into one with Gulp?