位串最近邻搜索

Question

我有数十万个长度为32位的稀疏位串。

我想对它们进行最近邻搜索，查找性能至关重要。我一直在阅读各种算法，但它们似乎针对的是文本字符串而不是二进制字符串。我认为局部敏感散列或谱散列似乎是很好的候选者，或者我可以考虑压缩。这些都能很好地解决我的位串问题吗？任何方向或指导都将非常感谢。

Answer 1

这里有一个快速而简单的方法，然后是一个以更多内存为代价具有更好性能的变体。

In:数组Uint X[]，例如1M 32位字

想要:一个带有小hammingdist( q, X[j] )的函数near( Uint q ) --> j

方法:在排序的X中进行二进制搜索q，然后线性搜索它周围的一个块。

伪码：

def near( q, X, Blocksize=100 ):
    preprocess: sort X
    Uint* p = binsearch( q, X )  # match q in leading bits
    linear-search Blocksize words around p
    return the hamming-nearest of these.

这是很快的--在我的Mac上，Binary search 1M单词+最近的hammingdist在100大小的块中需要< 10我们。(这高度依赖于缓存-您的里程数会有所不同。)

这离找到真正的最接近的Xj有多近？我只能做实验，不能做数学运算：

对于1M个随机字中的1M个随机查询，最接近的匹配平均距离为4-5比特，而真正最近的匹配距离为3(线性扫描全部1M)：

near32  N 1048576  Nquery 1048576  Blocksize 100 
binary search, then nearest +- 50
7 usec
distance distribution: 0 4481 38137 185212  443211 337321 39979 235  0

near32  N 1048576  Nquery 100  Blocksize 1048576 
linear scan all 1048576
38701 usec
distance distribution: 0 0 7 58  35 0

运行块大小为50和100的数据，看看匹配距离是如何下降的。

​

为了更近，以两倍的内存为代价，

对交换了上/下半字的X复制Xswap，并返回较好的

​

near( q, X, Blocksize )
near( swap q, Xswap, Blocksize )

有了大量的内存，一个人可以使用更多的X的比特混洗副本，例如32次旋转。

我不知道Nshuffle和Blocksize的性能是如何变化的--这是LSH理论家的问题。

​

(添加)：为了接近匹配比特字符串，比方说320位，10个字，生成10个指针数组，按字0，字1排序...并使用如上的binsearch搜索块：

​

nearest( query word 0, Sortedarray0, 100 ) -> min Hammingdist e.g. 42 of 320
nearest( query word 1, Sortedarray1, 100 ) -> min Hammingdist 37
nearest( query word 2, Sortedarray2, 100 ) -> min Hammingdist 50
...
-> e.g. the 37.

这当然会错过没有单个单词接近的近匹配，但它非常简单，排序和binsearch非常快。指针数组占用的空间与数据位完全相同。100个字，3200位将以完全相同的方式工作。

但是:只有当0比特和1比特的数量大致相等时，这才有效，而不是99%0比特。

Answer 2

我刚刚读到一篇关于这个问题的论文。

Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering (Ravichandran et al，2005)

基本思想类似于Denis的答案(按位的不同排列按词典顺序排序)，但它包括一些额外的想法和关于该主题的文章的进一步参考。

它实际上是在https://github.com/soundcloud/cosine-lsh-join-spark中实现的，这就是我找到它的地方。