我正在寻找一种数据结构来处理包含 512 个二进制值的二进制字符串。
我的目标是将查询发送到结构并获取一个结果集，其中包含所有距离较小的数据。
我的第一个想法是使用 kd 树。但是这些树对于高维度来说非常慢。我的第二个想法是使用lsh方法（minHash/superbit）lsh。但为此，我还必须有一个结构来执行有效的搜索
知道如何处理这些大数据吗？
**更新**一些详细说明：
- 因为汉明距离只存在一个上限，可能是 128。但随着时间的推移，我不知道上限
- 插入或删除会很好，但我也可以重建图表（数据库每周只更新一次）
- 结果集必须包含所有相关节点（我不是在寻找 knn）
如果不知道您想要的搜索参数，就很难进行过多的优化。也就是说，我认为一个好的方法是构建一个 B 树或 T 树，然后针对数据的二进制性质优化该结构。
具体来说，您有 64 字节的数据作为 512 元素位字符串。您的估计是您将拥有"比利"的记录。这是 232 个值的数量级，所以 1/16的空间会满吗？（这符合你的期望吗？
无论如何，尝试将数据分解为字节，让每个字节都是一个键级别。如果设置位的概率是均匀的，则您可能可以压缩电平记录。（如果不是，如果说设置位更有可能在键的前面，那么你可能只想分配 256 个下一级指针，并让一些指针为 null。这并不总是值得的。
您的所有级别都将相同 - 它们将代表字符串的 8 位。因此，计算一个表，该表映射一个字节内的所有字节值，S距离该字节 0 <= S <= 8。此外，计算一个表，该表将两个字节映射到它们之间的距离 E，hamming(a,b) 。
要遍历树，请将搜索距离设为 SD。 设置 D = SD。 读取顶级块。查找块中的所有 8 位值，该值与查询的距离小于min(8, D)。对于每个值，计算确切的距离hamming(query, value)并递归到下块，并D = D - hamming(query, value)该子树。
我在这里看到的最大设计问题是闭包要求：对于任意 N，我们需要返回给定向量距离 N 内的所有项目。 数据空间是稀疏的："十亿"大约是 2^33，但我们有 512 位信息，所以每 2^（512-33） 可能性只有 1 个条目。 对于随机分布的密钥，任意两个节点之间的预期距离为 256;预计的最近邻距离约为 180。
这让我期望您的搜索将取决于非随机数据聚类，并且您的搜索将通过识别该聚类来促进。 对于初始数据来说，这将是一个有点痛苦的预处理步骤，但应该是值得的。
我对此的一般方法是首先以某种通常快速的方式识别这些集群。 从返回非常通用的距离指标的哈希函数开始。 例如，对于任何向量，计算到一组正交参考向量中每个向量的距离。 对于 16 位，您可以采用以下集合（以十六进制列出）：0000、00FF、0F0F、3333、5555，交替位的连续"颗粒"。 将此哈希作为简单元组返回 4 位距离，总共 20 位（长向量有实际节省，因为其中一个大小是 2^（2^N））。
现在，这个哈希元组允许您粗略估计汉明距离，以便您可以更轻松地对向量进行聚类：相似的向量必须具有相似的哈希值。
在每个聚类中，找到一个中心元素，然后通过与该中心的距离来表征聚类的每个元素。 为了获得更快的速度，请为每个节点提供其最近邻居的列表以及距离，所有这些相邻节点都在集群内。 这为您提供了每个集群的图形。
同样，连接所有聚类中心，为较近的聚类中心提供直接边。 如果你的数据是合理的，那么我们将能够保证，对于集群中心为Ac和Bc的任何两个节点A，B，我们将有d（A，Ac）+ d（B，Bc）
查询过程现在更快一些。 对于目标向量 V，找到哈希值。 查找足够接近其邻域中的某些内容可能匹配的聚类中心（[实际距离] - [查询范围] - [聚类半径]）。 这将允许您立即消除整个集群，并可能为您提供整个集群的"命中"。 对于每个边缘集群（一些，但不是所有节点都符合条件），您需要找到一个通过接近蛮力的节点（从距集群中心的可行距离范围的中间开始），然后对每个节点的邻居进行广度优先搜索。
我希望这将为您提供与最佳性能相当的东西。 它还可以很好地适应添加和删除，只要这些添加和删除的频率不足以更改其他节点的群集成员身份。
向量集很简单。 写出 16 位大小写的位模式：
0000 0000 0000 0000 16 0s
0000 0000 1111 1111 8 0s, 8 1s
0000 1111 0000 1111 4 0s, 4 1s, repeat
0011 0011 0011 0011 2 0s, 2 1s, repeat
0101 0101 0101 0101 1 0s, 1 1s, repeat