image - 查找相似字符串的索引策略

Question

我正在设计用于查找相似哈希值的索引策略。哈希是为图像生成的。即

String A = "00007c3fff1f3b06738f390079c627c3ffe3fb11f0007c00fff07ff03f003000" //Image 1
String B = "6000fc3efb1f1b06638f1b0071c667c7fff3e738d0007c00fff03ff03f803000" //Image 2

这两个哈希相似(基于汉明距离和 Levenshtein 距离)，因此图像相似。我有超过 1.9 亿个这样的哈希值。我必须选择合适的索引数据结构，其中查找相似散列的最坏情况复杂度不是 O(n)。哈希数据结构将不起作用，因为它会搜索 <、= 和 >(或者会搜索吗？)。我可以找到汉明距离或其他距离来计算相似度，但在最坏的情况下，我最终会计算它 1.9 亿次。

现在这是我的策略:

目前我正在研究 BTree，我将根据编号对节点中的所有键进行排名。连续相同的字符并遍历排名最高的键，如果子键的排名低于父节点中其他键的排名，我将开始遍历父节点中的那个键。如果父级的所有等级都相同，我将进行正常的 BTree 遍历(givenkey < nodeKey --> 转到 nodeKey 的子节点..使用 ASCII 比较)，这就是我的问题所在。

因为这会导致搜索中出现大量漏报。在最坏的情况下，我将只遍历树的一部分，在其他遍历中可以找到可能相似的键。否则我必须搜索整棵树，这又是 O(n)，我可能还没有树。

我觉得必须有更好的方法，现在我被困住了，很高兴听到任何关于解决问题的意见。请分享您的想法。

附:我不能使用任何外部数据库。

Answer 1

首先，这是一个非常难的问题。不要指望整洁的答案。

我见过的一个大概的数据结构是Spatial Approximation Sample Hierarchy (SASH) .

A SASH (Spatial Approximation Sample Hierarchy) is a general-purpose data structure for efficiently computing approximate answers for similarity queries. Similarity queries naturally arise in a number of important computing contexts, in particular content-based retrieval on multimedia databases, and nearest-neighbor methods for clustering and classification.

SASH 仅使用距离函数来构建数据结构，因此距离函数(在您的情况下，图像哈希函数也是如此)需要“良好”。基本的直觉大致是，如果 A ~ B(图像 A 接近图像 B)和 B ~ C，那么通常是 A ~ C。数据结构在相对接近的项目之间创建链接，并且您可以通过仅查看来修剪搜索对于更接近您的查询的事物。该策略是否真的有效取决于数据的性质和距离函数。

自从我关注 SASH 以来已经有 10 年左右的时间了，所以可能还有更新的发展。 Michael Houle's page似乎表明他对一种叫做 Rank Cover Trees 的东西有更新的研究，其目的似乎与 SASH 相似。这至少应该让你开始在该领域进行研究；阅读一些论文并遵循引用线索。