compression - 位串最近邻搜索

Question

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

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

Answer 1

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

在:数组 Uint X[]，例如1M 32 位字
通缉:一个函数near( Uint q ) --> j 带小 hammingdist( q, X[j] )方法:二分查找q已排序 X ,
然后在它周围线性搜索一个块。
伪代码:

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.

这很快——
Binary search 100万字
+ 大小为 100 的块中最近的 hammingdist
在我的 Mac ppc 上需要 < 10 us。
(这是高度依赖缓存的——你的里程会有所不同。)

这与找到真正最近的 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
看看比赛距离是如何下降的。

为了更接近，以两倍的内存为代价，
复制 Xswap的 X交换上/下半字，
并返回更好的

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.

这当然会错过没有一个单词接近的接近匹配，
但它非常简单，而且 sort 和 binsearch 非常快。
指针数组占用的空间与数据位完全一样。
100 个字、3200 位的工作方式完全相同。
但是:这仅在 0 位和 1 位的数量大致相等时才有效，
不是 99% 0 位。