MySQL或PostgreSQL的汉明距离优化？

Question

MySQL或PostgreSQL的汉明距离优化？

mysqlsqlquery-optimizationhamming-distancephash

6

我正在尝试改进在MySQL数据库中搜索相似图像的pHash技术。目前，我按照以下方式比较pHash计数汉明距离：

SELECT * FROM images WHERE BIT_COUNT(hash ^ 2028359052535108275) <= 4

选择 (引擎 MyISAM) 的结果如下：

20000行；查询时间<20毫秒
100000行；查询时间约为60毫秒＃在达到150000行之前一切都很好
300000行；查询时间约为150毫秒

因此，查询时间取决于表中行数的增加。

我还尝试了在stackoverflow上找到的解决方案：SQL中二进制字符串的海明距离

SELECT * FROM images WHERE 
BIT_COUNT(h1 ^ 11110011) + 
BIT_COUNT(h2 ^ 10110100) + 
BIT_COUNT(h3 ^ 11001001) + 
BIT_COUNT(h4 ^ 11010001) + 
BIT_COUNT(h5 ^ 00100011) + 
BIT_COUNT(h6 ^ 00010100) + 
BIT_COUNT(h7 ^ 00011111) + 
BIT_COUNT(h8 ^ 00001111) <= 4

行数300000; 查询时间约为240毫秒。

我将数据库引擎改为PostgreSQL。将此MySQL查询翻译为PyGreSQL，但没有成功。行数300000; 查询时间约为18秒。

是否有任何解决上述查询的最佳方案？ 我的意思是与行数无关的优化。

我有限制的方式（工具）来解决这个问题。到目前为止，MySQL似乎是最简单的解决方案，但我可以在专用机器上使用Ruby部署代码，使其能够与每个开源数据库引擎一起使用。有一些现成的MsSQL解决方案https://stackoverflow.com/a/5930944/766217（未经测试）。也许有人知道如何将其翻译为MySQL或PostgreSQL。

请基于某些代码或观察结果发布答案。我们在stackoverflow.com上有很多关于汉明距离的理论问题。

谢谢！

- mateuszdw

嘿，我正在尝试做一个类似的图像搜索，就像你一样。但是我总是返回0？你能给我提供关于哈希字符串相关搜索的示例代码吗？ - TomSawyer

3个回答

3

在算法效率方面，计算机科学家使用“阶”的概念来表示，用O(something)表示其中something是n的函数，即正在计算的事物的数量，在本例中是行数。因此，时间按升序排列:

O(1)——与项目数量无关
O(log(n))——随着项目的对数增加
O(n)——与项目数量成比例（你所拥有的）
O(n^2)——随项目的平方增加
O(n^3)——等等
O(2^n)——呈指数增长
O(n!)——随数字的阶乘增加而增加

对于任何合理的n（80+），最后2个都是无法计算的。

只有最重要的项才是最重要的，因为在大n时这会支配，因此n^2和65*n^2+787*n+4656566都是O(n^2)。

请记住，这是一个数学构造，算法在真实软件上使用真实数据的真实硬件上花费的时间可能会受到其他因素的影响（例如，O(n^2)内存操作可能比O(n)磁盘操作花费更少的时间）。

对于您的问题，您需要遍历每一行并计算BIT_COUNT(hash ^ 2028359052535108275) <= 4。这是一个O(n)操作。

唯一可以改进的方法是利用索引，因为b树索引检索是一个O(log(n))操作。

但是，由于您的列字段包含在函数中，因此无法在该列上使用索引。你有2种可能性:

这是SQL服务器解决方案，我不知道它是否可移植到MySQL。在表中创建一个持续计算列并使用公式BIT_COUNT(hash ^ 2028359052535108275)在其上放置一个索引。如果您需要更改位掩码，则不适用于此。
找出一种不使用BIT_COUNT函数进行按位运算的方法。

- Dale M

解决方案1不能使用，因为每次请求都需要更改位掩码。解决方案2太抽象-看起来我有解决方案，但我不能说，因为我想赚钱 :) - happy_marmoset

编写Postgres扩展可以是一个解决方案，如果您精通C语言。工作项目https://github.com/lalinsky/acoustid-server/blob/master/postgresql/acoustid_compare.c - mateuszdw

顺便提一下，你可以使用树结构来加速这种查询。你可以使用BK树，它可以在O(log(n))的时间内完成（尽管距离会显著影响n的值）。无论如何，你可以将完整的表扫描减少到小于10%的表扫描（对于编辑距离小于等于2的情况，在许多情况下）。 - Fake Name

0

这是我的测试结果。Phash使用Python中的imagehash库计算，并以两个BIGINTs的形式存储在数据库中。

在不使用分片的mariadb数据库中运行了858,433个图像的测试。我发现分片实际上会减慢进程，但是这是使用函数方法进行的，因此在没有它或较大的数据库上可能会有所不同。

这些正在运行的表是一个仅内存表。本地表被保存，并且在启动数据库时，id、phash1和phash2被复制到内存表中。一旦找到某些内容，就会返回id以匹配innodb表。

总图像数：858433

图像1：ece0455d6b8e9470

函数HAMMINGDISTANCE_16：

RETURN BIT_COUNT(A0 ^ B0) + BIT_COUNT(A1 ^ B1)

方法：HAMMINGDISTANCE_16 函数

查询：

SELECT `id` FROM `phashs` WHERE HAMMINGDISTANCE_16(filephash_1, filephash_2, CONV(SUBSTRING('ece0455d6b8e9470', 1,  8), 16, 10), CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) <= 3;

时间：2.1760秒

方法：BIT_COUNT

查询：

SELECT `id` FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1,  8), 16, 10)) +  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) <= 3;

时间：0.1547秒

方法：多选BIT_COUNT内部是filephash_1

查询：

SELECT `id` FROM ( SELECT `id`, `filephash_2`, BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1, 8), 16, 10)) as BC0 FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1, 8), 16, 10)) <= 3 ) BCQ0 WHERE BC0 + BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9, 8), 16, 10)) <= 3;

时间：0.1878秒

方法：多选BIT_COUNT内部是filephash_2

查询：

SELECT `id` FROM (SELECT `id`, `filephash_1`, BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) as BC1 FROM `phashs` WHERE  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) <= 3) BCQ1 WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1,  8), 16, 10)) + BC1   <= 3;

时间：0.1860秒

图片2：813ed36913ec8639

函数HAMMINGDISTANCE_16：

RETURN BIT_COUNT(A0 ^ B0) + BIT_COUNT(A1 ^ B1)

方法：HAMMINGDISTANCE_16 函数查询：

SELECT `id` FROM `phashs` WHERE HAMMINGDISTANCE_16(filephash_1, filephash_2, CONV(SUBSTRING('813ed36913ec8639', 1,  8), 16, 10), CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) <= 3;

时间：2.1440秒

方法：BIT_COUNT 查询：

SELECT `id` FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1,  8), 16, 10)) +  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) <= 3;

时间：0.1588秒

方法：多选BIT_COUNT内的是filephash_1

查询：

SELECT `id` FROM ( SELECT `id`, `filephash_2`, BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1, 8), 16, 10)) as BC0 FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1, 8), 16, 10)) <= 3 ) BCQ0 WHERE BC0 + BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9, 8), 16, 10)) <= 3;

时间：0.1671秒

方法：多选BIT_COUNT内部是filephash_2

查询：

SELECT `id` FROM (SELECT `id`, `filephash_1`, BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) as BC1 FROM `phashs` WHERE  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) <= 3) BCQ1 WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1,  8), 16, 10)) + BC1   <= 3;

时间：0.1686秒

- Daniel Weisinger

由于您当前的回答表述不清，请[编辑]以添加更多细节，帮助其他人了解如何解决所提出的问题。您可以在帮助中心找到有关编写良好答案的更多信息。 - Bruno

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

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

- alfadog67 · Accepted Answer

这个解决方案对我来说使速度更快了一些。它为每个哈希比较生成一个派生表，并仅返回小于汉明距离的结果。这样，它不会在已经超过汉明距离的pHash上执行BIT_COUNT。它在260万条记录中以大约2.25秒返回所有匹配项。这是InnoDB，我很少有索引。如果有人能让它更快，我将感激不尽。

SELECT *, BIT_COUNT(pHash3 ^ 42597524) + BC2 AS BC3 
FROM ( 
    SELECT *, BIT_COUNT(pHash2 ^ 258741369) + BC1 AS BC2 
    FROM ( 
        SELECT *, BIT_COUNT(pHash1 ^ 5678910) + BC0 AS BC1 
        FROM ( 
            SELECT `Key`, pHash0, pHash1, pHash2, pHash3, BIT_COUNT(pHash0 ^ 1234567) as BC0 
            FROM files 
            WHERE  BIT_COUNT(pHash0 ^ 1234567) <= 3 
        ) AS BCQ0 
        WHERE BIT_COUNT(pHash1 ^ 5678910) + BC0 <= 3 
    ) AS BCQ1 
    WHERE BIT_COUNT(pHash2 ^ 258741369) + BC1 <= 3 
    ) AS BCQ2 
WHERE BIT_COUNT(pHash3 ^ 42597524) + BC2 <= 3

这是等效的查询，但没有衍生表。它的返回时间几乎是原来的三倍。

SELECT `Key`, pHash0, pHash1, pHash2, pHash3 
FROM Files 
WHERE BIT_COUNT(pHash0 ^ 1234567) + BIT_COUNT(pHash1 ^ 5678910) + BIT_COUNT(pHash2 ^ 258741369) + BIT_COUNT(pHash3 ^ 42597524) <=3

请记住，第一个值越低，运行速度就越快。