postgres 中的快速汉明距离查询

Question

我有一个包含图像感知哈希的大型数据库（1600 万行）。

我希望能够在合理的时间范围内通过汉明距离搜索行。

目前，就我正确理解这个问题而言，我认为这里最好的选择是实现BK-Tree的自定义 SP-GiST 实现，但这似乎需要做很多工作，而且我对实际操作仍然很模糊正确实施自定义索引的详细信息。计算汉明距离很容易处理，不过我确实知道 C。

基本上，这里合适的方法是什么？我需要能够在哈希的特定编辑距离内查询匹配项。据我了解，等长字符串的 Levenshtein 距离在功能上是汉明距离，所以至少有一些现有的支持我想要的东西，虽然没有明确的方法从中创建索引（请记住，我正在查询的值变化。我无法预先计算与固定值的距离，因为那只会对那个值有用）。

散列当前存储为包含散列的二进制 ASCII 编码的 64 字符字符串（例如“10010101...”），但我可以很容易地将它们转换为 int64。真正的问题是我需要能够相对快速地进行查询。

看起来这可能是可能实现沿着什么，我想用线的东西pg_trgm，但我对如何卦匹配mechamism作品有点不清楚（特别是，什么是相似性量度它返回实际上代表什么？它看起来有点像编辑距离）。

插入性能并不重要（计算每一行的哈希值在计算上非常昂贵），所以我主要关心搜索。

Answer 1

摩尔答案！

好的，我终于花时间写了一个自定义的 PostgreSQL 索引扩展。我使用了SP-GiST 接口。

这相当具有挑战性，主要是因为 Posgres很大。

不管怎么说，像往常一样，它在GitHub的了这里。

在性能方面，它目前比我对这个问题的另一个答案中的纯内存实现慢约 2-3 倍，但使用起来方便得多，我很乐意吃掉性能损失（实际上，它是约 50 ms/query - 150 ms/query，仍然很小）。

Answer 2

好吧，我花了一段时间研究编写自定义 postgres C 扩展，最后只编写了一个 Cython 数据库包装器，该包装器在内存中维护 BK 树结构。

基本上，它维护来自数据库的 phash 值的内存副本，并且对数据库的所有更新都重播到 BK 树中。

这一切都在github这里。它也有很多单元测试。

跨 1000 万个哈希值的数据集查询距离为 4 的项目会导致触及树中约 0.25%-0.5% 的值，并需要约 100 毫秒。