5

我试图改进在 MySQL 数据库中搜索相似图像 pHashed。现在我像这样比较 pHash 计数汉明距离：

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

选择结果（引擎 MyISAM）

  • 20000 行；查询时间 < 20ms
  • 100000 行；query time ~ 60ms # 这很好，直到达到 150000 行
  • 300000 行；查询时间 ~ 150ms

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

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

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 ; 查询时间 ~ 240ms

我将数据库引擎更改为 PostgreSQL。将此 MySQL 查询转换为 PyGreSQL 没有成功。行 300000 ; 查询时间~18s

有没有优化上述查询的解决方案？ 我的意思是优化不取决于行数。

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

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

谢谢！

4

2 回答 2

3

在考虑算法的效率时，计算机科学家使用表示为 O(something) 的顺序的概念，其中 something 是 n 的函数，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-tree 索引检索是 O(log(n)) 操作。

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

  1. 这是一个 SQL 服务器解决方案，我不知道它是否可以移植到 MySQL。使用公式在表中创建一个持久计算列BIT_COUNT(hash ^ 2028359052535108275)并在其上放置一个索引。如果您需要更改位掩码，这将不合适。
  2. 找出一种不使用 BIT_COUNT 函数进行按位运算的方法。
于 2013-02-19T03:27:28.010 回答
2

这个解决方案让我的事情变得更快了。它为每个哈希比较创建一个派生表，并仅返回小于 ham 距离的结果。这样，它就不会对已经超过 ham 的 pHash 执行 BIT_COUNT。它会在大约 2.25 秒内返回 260 万条记录的所有匹配项。

它是 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

这是等效的查询，但没有派生表。它的返回时间几乎是它的 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

请记住，第一个的火腿值越低，它运行得越快。

于 2014-08-12T20:22:33.507 回答