MySQL或PostgreSQL的汉明距离优化？

Question

我试图在MySQL数据库中改进搜索类似图像的pHashed.现在我比较pHash计算汉明距离像这样:

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

选择结果(引擎MyISAM)

• 20000行; 查询时间<20ms
• 100000行; 查询时间~60ms#这很好,直到达到150000行
• 30万行; 查询时间~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的现成解决方案/sf/answers/415166111/(未经测试).也许有人知道如何为MySQL或PostgreSQL翻译它.

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

谢谢!

Answer 1

在考虑算法的效率时，计算机科学家使用表示为 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种可能性：

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