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

前端之家收集整理的这篇文章主要介绍了数据库 – 用于查找具有相似位值的附近键的数据结构前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
@H_502_1@我有一些数据,高达一百万到十亿条记录,每个数据由位域表示,每个密钥大约64位.这些位是独立的,你可以想象它们基本上是随机位.

如果我有一个测试键,我想用相同的键查找我的数据中的所有值,哈希表将很容易地吐出来,在O(1)中.

什么算法/数据结构将有效地查找与查询键最相似的所有记录?这里类似的意思是大多数位是相同的,但是最小的数字被允许是错误的.这通常由Hamming distance.测量,它只是计算不匹配位数.

有两种方式可能会进行此查询,可能是通过指定不匹配率,例如“给我一个所有现有密钥的列表,其中所有现有的密钥有少于6位,不同于我的查询”或简单的最佳匹配,如“给我一个具有我查询中不同位数最少的10,000个密钥的列表.

你可能会跑到k-nearest-neighbor algorithms,但是在这里我们谈论的是独立的位,所以似乎没有像四叉树这样的结构是有用的.

这个问题可以通过简单的强力测试来解决,这个哈希表用于低位数的不同位.如果我们想要查找与查询不同的所有键,例如,我们可以枚举所有64个可能的键并测试它们.但是这个爆炸很快,如果我们想允许两位差异,那么我们必须探测64 * 63 = 4032次.对于较高的位数,它的指数变差.

那么还有另一种数据结构或策略使得这种查询更有效率?
数据库/结构可以根据需要进行预处理,这是应优化的查询速度.

解决方法

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

BK-tree通常用参考文本描述,并使用levenshtein距离构建树,但直接用二进制串和汉明距离来写一个.

猜你在找的MsSQL相关文章