SPW*_*ley 10 database language-agnostic algorithm math hash
我有一些数据,最多可达一百万到十亿条记录,每条记录由一个位域表示,每个键大约64位.这些位是独立的,您可以将它们想象成基本上随机的位.
如果我有一个测试密钥,并且我想用相同的密钥查找数据中的所有值,则哈希表将很容易地在O(1)中吐出这些值.
什么算法/数据结构可以有效地找到与查询键最相似的所有记录？这里类似意味着大多数位是相同的,但允许最小数量是错误的.传统上通过汉明距离来测量 .,它只计算不匹配位的数量.
有两种方法可以进行此查询,一种可能是通过指定不匹配率,例如"给我一个列表,其中包含少于6位且与我的查询不同的所有现有键",或者只是通过最佳匹配,例如"给我一个10,000条密钥的列表,其中我的查询中的不同位数最少."
您可能会想要运行k-最近邻居算法,但在这里我们讨论的是独立位,因此像四叉树这样的结构似乎不太有用.
这个问题可以通过简单的强力测试哈希表来解决少量不同的比特.例如,如果我们想要查找与查询相差一位的所有键,我们可以枚举所有64个可能的键并对它们进行全部测试.但是这很快爆发,如果我们想要允许两位差异,那么我们必须探测64*63 = 4032次.对于更高的位数,它会呈指数级变差.
那么是否有其他数据结构或策略可以使这种查询更有效？可以根据需要对数据库/结构进行预处理,这是应该优化的查询速度.