位串上 top-k 查询的索引结构
Index structure for top-k queries on bitstrings
给定比特串数组（所有长度相同）和查询字符串 Q 找到与 Q 最相似的前 k 个字符串，其中字符串 A 和 B 之间的相似性定义为 A 和 B 中 1 的数量，（操作并按位应用）。
我觉得这个问题应该有一个经典的结果。
k很小，以百为单位，而向量数以亿为单位，向量长度为512或1024
解决此问题的一种方法是使用 Russell-Rao 相似函数构建 K-Nearest Neighbor Graph (K-NNG)（有向图）。
请注意，高效的 K-NNG 构造仍然是一个悬而未决的问题，并且 none 这个问题的已知解决方案是通用的、高效的和可扩展的 [引用自 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). Note that Russell-Rao similarity is not a metric (see Properties of Binary Vector Dissimilarity Measures - Zhang, Srihari 2003）：“if”的“d( x, y) = 0 当且仅当 x == y" 为假。
在 A Fast Algorithm for Finding k-Nearest Neighbors with Non-metric Dissimilarity - Zhang, Srihari 2002 中，作者提出了一种快速分层搜索算法，使用二元向量中的非度量度量来查找 k-NN space。他们使用参数二元向量距离函数 D(β)。当 β=0 时，该函数简化为 Russell-Rao 距离函数。我不会称它为 "classical result"，但这是我能找到的唯一一篇研究这个问题的论文。
您可能需要查看这两项调查：On nonmetric similarity search problems in complex domains - Skopal, Bustos 2011 and A Survey on Nearest Neighbor Search Methods - Reza, Ghahremani, Naderi 2014。也许你会发现我遗漏的东西。
这个问题可以通过编写简单的 Map 和 Reduce 作业来解决。我既没有声称这是最佳解决方案，也没有声称这是唯一解决方案。
另外，您在评论中透露，k 以数百为单位，有数百万个位串，每个位串的大小为 512 或 1024。
映射器伪代码：
- 给定 Q;
- 对于每个位串 b，计算 similarity = b & Q
- 发出(相似度, b)
现在，组合器可以合并来自每个映射器的具有相同相似性的所有位串的列表。
Reducer 伪代码：
- 消耗（相似度，listOfBitStringsWithThisSimilarity）；
- 按相似度值降序输出。
从 reducer 的输出中，您可以提取前 k 个位串。
因此，MapReduce 范式可能是您正在寻找的经典解决方案。
给定比特串数组（所有长度相同）和查询字符串 Q 找到与 Q 最相似的前 k 个字符串，其中字符串 A 和 B 之间的相似性定义为 A 和 B 中 1 的数量，（操作并按位应用）。
我觉得这个问题应该有一个经典的结果。
k很小，以百为单位，而向量数以亿为单位，向量长度为512或1024
解决此问题的一种方法是使用 Russell-Rao 相似函数构建 K-Nearest Neighbor Graph (K-NNG)（有向图）。
请注意，高效的 K-NNG 构造仍然是一个悬而未决的问题，并且 none 这个问题的已知解决方案是通用的、高效的和可扩展的 [引用自 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). Note that Russell-Rao similarity is not a metric (see Properties of Binary Vector Dissimilarity Measures - Zhang, Srihari 2003）：“if”的“d( x, y) = 0 当且仅当 x == y" 为假。
在 A Fast Algorithm for Finding k-Nearest Neighbors with Non-metric Dissimilarity - Zhang, Srihari 2002 中，作者提出了一种快速分层搜索算法，使用二元向量中的非度量度量来查找 k-NN space。他们使用参数二元向量距离函数 D(β)。当 β=0 时，该函数简化为 Russell-Rao 距离函数。我不会称它为 "classical result"，但这是我能找到的唯一一篇研究这个问题的论文。
您可能需要查看这两项调查：On nonmetric similarity search problems in complex domains - Skopal, Bustos 2011 and A Survey on Nearest Neighbor Search Methods - Reza, Ghahremani, Naderi 2014。也许你会发现我遗漏的东西。
这个问题可以通过编写简单的 Map 和 Reduce 作业来解决。我既没有声称这是最佳解决方案，也没有声称这是唯一解决方案。
另外，您在评论中透露，k 以数百为单位，有数百万个位串，每个位串的大小为 512 或 1024。
映射器伪代码：
- 给定 Q;
- 对于每个位串 b，计算 similarity = b & Q
- 发出(相似度, b)
现在，组合器可以合并来自每个映射器的具有相同相似性的所有位串的列表。
Reducer 伪代码：
- 消耗（相似度，listOfBitStringsWithThisSimilarity）；
- 按相似度值降序输出。
从 reducer 的输出中，您可以提取前 k 个位串。
因此，MapReduce 范式可能是您正在寻找的经典解决方案。