algorithm - 位串上 top-k 查询的索引结构

Question

给定比特串数组(所有长度相同)和查询字符串 Q 找到与 Q 最相似的前 k 个字符串，其中字符串 A 和 B 之间的相似性定义为 A 和 B 中 1 的数量，(操作和是按位应用)。

我认为这个问题应该有一个经典的结果。

k很小，以百为单位，而向量个数以亿为单位，向量长度为​​512或1024

Answer 1

解决这个问题的一种方法是构造一个 K-Nearest Neighbor Graph (K-NNG) (有向图)具有 Russell-Rao 相似度函数。

请注意，高效的 K-NNG 构造仍然是一个悬而未决的问题，并且该问题的已知解决方案都不是通用的、高效的和可扩展的 [引自 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)。请注意，Russell-Rao 相似度不是 metric (参见 Properties of Binary Vector Dissimilarity Measures - Zhang, Srihari 2003):“d(x, y) = 0 iff x == y”的“if”部分为假。

在A Fast Algorithm for Finding k-Nearest Neighbors with Non-metric Dissimilarity - Zhang, Srihari 2002 ，作者提出了一种快速分层搜索算法，以在二进制向量空间中使用非度量度量来查找 k-NN。他们使用参数二元向量距离函数 D(β)。当 β=0 时，该函数简化为 Russell-Rao 距离函数。我不会称之为“经典结果”，但这是我能找到的唯一一篇研究这个问题的论文。

您可能需要检查这两个调查:On nonmetric similarity search problems in complex domains - Skopal, Bustos 2011和 A Survey on Nearest Neighbor Search Methods - Reza, Ghahremani, Naderi 2014 .也许您会发现我遗漏的东西。