501*_*ted 7 distance bigdata hamming-distance
我正在寻找一个数据结构来处理包含512个二进制值的二进制字符串.
我的目标是向结构发送查询并获取包含距离较远的所有数据的结果集.
我的第一个想法是使用kd树.但是这些树木的高度非常慢.我的第二个想法是使用lsh方法(minHash/superbit)lsh.但为此,我还必须有一个结构来执行有效的搜索
任何想法如何处理这些大数据？
**更新**一些细节说明:
如果不知道您想要的搜索参数，就很难进行过度优化。也就是说，我认为一个好的方法是构建 B 树或 T 树，然后针对数据的二进制性质优化该结构。
具体来说，您有 64 字节的数据作为 512 个元素的位串。您估计您将拥有“数十亿”条记录。这大约是 2 32 个值，所以 1/16的空间将被填满？（这符合你的期望吗？）
不管怎样，尝试将数据分成字节，让每个字节都是一个关键级别。如果设置位的概率是均匀的，您可能可以压缩级别记录。（如果不是，如果说设置位更有可能位于键的前面，那么您可能只想分配 256 个下一级指针并让其中一些为空。这并不总是值得的。）
您的所有级别都将相同 - 它们将代表字符串的 8 位以上。因此，计算一个表，对于一个字节，映射与该字节距离 0 <= S <= 8 内的所有字节值。S此外，计算一个表，将两个字节映射到它们之间的距离 E hamming(a,b)。
要遍历这棵树，请让您的搜索距离为 SD。设 D = SD。阅读顶层块。查找块中min(8, D)距查询距离小于的所有 8 位值。对于每个值，计算精确距离hamming(query, value)并递归到D = D - hamming(query, value)该子树的较低块。