用于查找具有相似位值的附近键的数据结构

你想要的是 BK-Tree . 它是一种非常适合索引度量空间的树(您的问题是,它支持最近邻查询和距离查询)。我写 an article 不久前的事。

BK树通常是参照文本和使用Levenshtein距离来构建树的,但是用二进制字符串和Hamming距离来编写它是很简单的。

这听起来很适合S-Tree,它就像一个层次颠倒的文件。关于这个主题的好资源包括以下论文:

Hierarchical Bitmap Index: An Efficient and Scalable Indexing Technique for Set-Valued Attributes.

Improved Methods for Signature-Tree Construction (2000)

引自第一个:

分层位图索引e_很好地支持不同的- 查询的不同类,包括子集、超集和相似性查询。 实验表明,层次位图索引的性能优于 其他集合索引技术很有意义。

这些论文包括对其他可能有用的研究的参考,例如 M-Trees .

创建二叉树(特别是 trie )用以下方式表示开始集中的每个键:根节点是空字,向下移动树到左边会附加0,向下移动右键会附加1。树的叶数将与起始集的元素数相同,因此大小应保持可控。

现在,您可以对该树进行递归遍历,在执行的每一个递归行中,最多允许与查询键有N个“偏差”,直到您在开始集合中找到在该偏差数范围内的所有节点为止。

我愿意和你一起去 inverted index 像搜索引擎一样。基本上你有64个固定词汇表。然后通过汉明距离来测量相似性,而不是像搜索引擎希望使用的余弦相似性。构建索引会很慢,但是您应该能够以正常的搜索引擎速度进行查询。

书 Introduction to Information Retrieval 包括倒排索引的高效构造、存储、压缩和查询。

"Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions" 从2008年开始,这似乎是迄今为止最好的结果。我一年多以前读过这本书,而且它毛茸茸的,所以我不想总结。这是从一页 locality-sensitive hashing 以及该方案的早期版本的实现。对于更一般的指针,请阅读 nearest neighbor search .

以前有人问过这种问题: Fastest way to find most similar string to an input?

数据库/结构可以是 预处理为 随你喜欢

好。。。 如果 那是真的。那么你所需要的就是一个汉明距离的相似度矩阵。通过大距离修剪使矩阵稀疏。它不会变快,也不会像记忆猪那么多。

好吧,您可以将所有相邻的键和原始键一起插入。这意味着对于k个不同的位,您存储(64选择k)倍的数据,它将要求您预先决定k。尽管您可以通过强制查询邻居来扩展k,但这将自动查询您插入的邻居的邻居。这也给了你一个时空权衡:例如,如果你接受一个64倍的数据放大和64倍的慢,你可以得到两位的距离。

我还没有完全想清楚,但我知道从哪里开始。

你可以把搜索空间分成 桶 每个桶都有一个 桶键 桶中的钥匙是与这个桶钥匙更相似的钥匙,而不是任何其他桶钥匙。要创建bucket密钥,您可以随机生成64位密钥并丢弃任何与以前创建的bucket密钥太近的密钥,或者您可以制定一些生成完全不同的密钥的算法。要找到与测试密钥最接近的密钥,首先要找到最接近的bucket密钥,然后测试bucket中的每个密钥。(实际上,最近的钥匙可能在另一个桶中,但不太可能在另一个桶中-您需要找到最近的钥匙,还是非常近的钥匙足够好?)

如果你对概率方法没意见的话,我认为有一个很好的方法来解决问题2。我假设你有2^30的数据和 cutoff 你想找到里面所有的点 截止 距离 test .

One_Try()
    1. Generate randomly a 20-bit subset S of 64 bits
    2. Ask for a list of elements that agree with test on S (about 2^10 elements)
    3. Sort that list by Hamming distance from test 
    4. Discard the part of list after cutoff

你重复 One_Try 在合并列表时尽可能多。你的尝试次数越多,你发现的点数就越多。例如,如果 x 在5位之内,你会在一次尝试中找到它,大约(2/3)^5=13%的概率。因此,如果你重复100次尝试,你会发现除了大约10 ^-6以外的所有尝试。 X . 总时间: 100*(1000*log 1000) .

这样做的主要优点是,您可以在继续操作时输出问题2的答案,因为在前几次尝试之后,您肯定会发现距离内的所有内容都不超过3位,等等。

如果你有很多台计算机,你会给它们中的每一台进行多次尝试,因为它们是完全可并行的:每台计算机都会提前保存一些哈希表。

• 此处描述的大型集合的数据结构: Detecting Near-Duplicates for Web Crawling 或
• 记忆中的特里: Judy-arrays at sourceforge.net

假设您必须访问每一行来测试它的值(或者如果对位字段进行索引,则对每个索引项进行索引),那么您可以使用

异或B

要找到不同的位,然后使用如下技术对结果进行位计数 this .

这实际上给了你汉明距离。

因为每个测试可以编译成数十条指令,所以运行速度非常快。

如果您对随机算法(在本例中是蒙特卡罗)没问题,可以使用 minhash .

如果数据不是那么稀疏,那么一个以关键点作为顶点和边的图连接“相邻”(Hamming Distance=1)节点可能是非常有效的时间方面。但是空间会很大,所以在你的情况下,我不认为这是一个值得的折衷。