位串最近邻搜索

Question

我有数十万个长度为32位的稀疏比特串.

我想对它们进行最近邻搜索，查找性能至关重要。我一直在研究各种算法，但它们似乎针对的是文本字符串而不是二进制字符串。我认为局部敏感哈希或谱哈希似乎是很好的选择，或者我可以研究压缩。这些方法中哪一个对我的比特串问题有效？任何方向或指导将不胜感激。

- user1305541

---

你能提供更多关于问题的信息吗？具体来说，“最近”的意思是什么？此外，这些位串是否有有趣的统计特性，比如零位或一位的数量，或者它们在32位字中的位置？@Denis猜得不错，但在尝试回答之前，我想要确认一下。顺便说一句，欢迎来到Stack Overflow！ - Randall Cook

Answer 1

我刚刚看到了一篇论文，解决了这个问题。

基本思想类似于Denis的答案（按位不同排字典序），但它包括许多其他想法和更多关于该主题的文章参考。

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

- Daniel Darabos

---

测试数据，有人吗？稀疏模式差异巨大，因此方法A可能在这里更好，方法B则更好。此外，真实数据激励实验者。 - denis

Answer 2

以下是一个快速且简单的方法，然后是一种在性能上更好但需要更多内存的变体。

输入：数组Uint X[]，例如1M个32位字

期望输出：一个函数near(Uint q)——> j，其中hammingdist(q,X[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.

这很快 - 二分查找在1M个单词中+在100个大小的块中找到最近的汉明距离，只需要<10微秒就能在我的Mac ppc上完成。 （这高度依赖于缓存 - 您的里程表可能会有所不同。）

这与找到真正最接近的X[j]有多接近？ 我只能做实验，无法进行数学计算：
对于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等排序，并使用上述的二分搜索查找块：

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.

当然，这种方法会错过那些没有单个单词接近的近似匹配， 但它非常简单，并且sort和binsearch非常快速。 指针数组所占据的空间正好与数据位一样多。 100个字，3200个位可以完全以同样的方式工作。
但是：只有在0位和1位数量大致相等时才有效， 而不是99%的0位。

- denis

---

有很多内存的话，可以使用更多位洗牌后的X副本，例如32个旋转。这并不需要额外的内存。只需编写修改过的快速排序算法，按照不同的顺序查看比特位即可。 - Daniel Darabos

是的，你说得对。对于1M x 1M位，密度为0.001（你在stats.stackexchange上的问题，在这里重新提问？），我认为问题在于如何找到密度约为0.5的切片或图像。许多具有100个共同位的行对是否意味着许多不相关的特征，列全部为0或单个1？ - denis

我在我的问题中添加了一个有用的示例应用程序：这些功能可以是描述人员移动的位置-时间对。全零列将是在给定时间为空的地方。我们肯定可以删除这些。 - Daniel Darabos

我偶然发现了一篇相关文章，它提出了几乎相同的算法：http://dl.acm.org/citation.cfm?id=1219917。（我已经将其作为答案添加了。）这对我的情况来说比对OP更有趣，因为它包括了从高维空间到低维空间的转换。 - Daniel Darabos

交叉链接至Daniel的问题：http://stats.stackexchange.com/questions/171947/find-close-pairs-in-very-high-dimensional-space-with-sparse-vectors - denis

我认为二分查找不是一个正确的方法。比特串不在一维空间中。1000和0001看起来相似，但如果你使用二分查找并以0001作为输入，你可能会发现最接近的项是0011，这是错误的。 - 柯鴻儀