哪种数据结构适合存储二进制字符串并使用汉明距离查询？

Question

哪种数据结构适合存储二进制字符串并使用汉明距离查询？

distancehamming-distancebigdata

7

我正在寻找一种数据结构来处理数十亿个包含512个二进制值的二进制字符串。

我的目标是向该结构发送查询，并获取结果集，其中包含所有距离较小的数据。

我的第一个想法是使用kd树。但是对于高维度，这些树非常慢。

我的第二个想法是使用lsh方法（minHash / superbit lsh）。但为此，我还必须拥有一个执行有效搜索的结构。

有没有任何想法来处理这些大数据？

** 更新 ** 一些详细说明：

- 对于汉明距离只存在一个可能是128的上限。但我不知道上限是多少。 - 插入或删除会很好，但我也可以重建图形（数据库每周只更新一次）。 - 结果集必须包含所有相关节点（我不在寻找knn）。

- 501 - not implemented

请澄清需求。这个结果集是否必须包含给定距离内的所有节点？距离是否有上限和下限？您能否承受索引和组织数据的大量开销？是否会有任何插入或删除操作？ - Prune

你好 Prune，是的，结果集应该包含所有在上限距离之下的节点。并没有下限。插入和删除操作会很不错，但我也可以重建图形。 - 501 - not implemented

查询和更改之间的比率是多少？数据库设计可能会根据更改（添加和删除）的相对频率而有所不同。 - Prune

此外，可能的距离值是多少？基于这个优化是否值得？ - aghast

这是什么类型的数据？此外，它是专有的吗？如果你有一个Github项目，我会很感兴趣。 - aghast

显示剩余2条评论

2个回答

1

这里最大的设计问题在于封闭要求：我们需要返回与给定向量距离N以内的所有项，对于任意的N。数据空间是稀疏的：“十亿”处于2^33的数量级，但我们只有512位的信息，因此每2^(512-33)个可能性只有1个条目。对于随机分布的键，任何两个节点之间的预期距离为256；预期的最近邻距离大约为180。

这导致我期望您的搜索将依赖于非随机的数据集群，并且通过识别该聚类来促进您的搜索。这将是初始数据上一步有些痛苦的预处理步骤，但应该是非常值得的。

我的一般做法是首先以一种通常较快的方式识别出这些簇。从一个返回非常通用距离度量的哈希函数开始。例如，对于任何向量，计算到一组正交参考向量的距离。对于16位，您可以采用以下集合（以十六进制列出）：0000、00FF、0F0F、3333、5555、交替位的连续“粒度”。将此哈希作为简单元组返回4位距离，总共20位（对于长向量实际节省，因为其中一个尺寸是2^(2^N)）。

现在，此哈希元组允许您大致估算汉明距离，以便更轻松地对向量进行聚类：相似的向量必须具有相似的哈希值。

在每个簇内，找到一个中心元素，然后通过其与该中心的距离来表征簇中的每个元素。为了加速，给每个节点一个最近邻居列表及其距离，所有这些距离都在簇内。这为每个簇提供了一个图形。

同样地，将所有的簇中心连接起来，直接将边连接到更近的簇中心。如果您的数据比较适合搜索，则我们可以保证对于任何两个节点A、B和它们的簇中心Ac、Bc，都满足d(A, Ac) + d(B, Bc) < d(A, B)。每个簇都是一个拓扑邻域。

查询过程现在有所加速。对于目标向量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

- Prune

1

明显的智力愚蠢；谢谢。编辑即将到来。 - Prune

嗨 Prune，你的方法听起来很棒！但是为什么你只使用16位进行第一次聚类呢？我应该如何描述这样的哈希度量呢？ - 501 - not implemented

我只使用16位来说明原理。将案例从16位扩展到512位，使用一组10个向量，距离占9位，哈希键总共占用90位。在什么意义上需要“描述”哈希键？ - Prune

啊，好的，谢谢。那么我就不需要其他哈希函数来描述键了。我会测试这些方法。目前我还不理解如何生成正交向量。是否有算法，或者必须通过暴力搜索并使用点积进行测试？ - 501 - not implemented

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aghast · Accepted Answer

不知道您预期的搜索参数是什么，很难进行过度优化。话虽如此，我认为一个好的方法是构建 B- 或 T- 树，然后优化该结构以适应数据的二进制特性。

具体来说，您有 64 字节的数据作为 512 元素的位串。您的估计是将有“数十亿”条记录。这大约是 2^32 个值的数量，因此空间的 1/16 将是满的？（是否符合您的预期？）

无论如何，尝试将数据分成字节，让每个字节成为键级别。如果集合位的概率是均匀的，您可能可以压缩级别记录。（如果不是，比如说设置位更可能在键的前面，那么您可能只想分配256个下一级指针，并使一些指针为空。这并不总是值得的。）

所有级别都将是相同的-它们将表示字符串的另外 8 位。因此，请计算一个表，将字节映射到与该字节距离为 S 的所有字节值，其中 0 <=S <=8。还要计算一个表，将两个字节映射到它们之间的距离 E，即 hamming(a,b)。

为了遍历树，请让您的搜索距离为 SD。设置 D = SD。读取顶层块。查找所有小于距离 min(8,D) 的块中的 8 位值。对于每个值，计算精确距离 hamming(query, value)，并使用 D= D-hamming(query,value) 递归到该子树的较低块。