MySQL或PostgreSQL的汉明距离优化？

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

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

选择结果(引擎MyISAM)

> 20000行;查询时间< 20ms的
> 100000行;查询时间~60ms#这很好,直到达到150000行
> 300000行;查询时间~150ms

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

我也尝试在stackoverflow上找到解决方案
Hamming distance on binary strings in 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;查询时间~240ms

我将数据库引擎更改为PostgreSQL. Translate this MySQL query to PyGreSQL
没有成功.
行300000;查询时间〜18s

有优化上述查询的解决方案吗？
我的意思是优化不依赖于行数.

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

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

谢谢！

最佳答案

在考虑算法的效率时,计算机科学家使用表示为O(某事物)的概念,其中某事物是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(O)花费更少的时间( n)磁盘操作).

对于您的问题,您需要遍历每一行并计算BIT_COUNT(hash ^ 2028359052535108275)< = 4.这是一个O(n)操作. 可以改进的唯一方法是利用索引,因为b树索引检索是O(log(n))操作. 但是,由于列字段包含在函数中,因此无法使用该列的索引.你有两种可能性：
>这是一个SQL服务器解决方案,我不知道它是否可以移植到MySQL.使用公式BIT_COUNT(hash ^ 2028359052535108275)在表中创建一个持久计算列,并在其上放置索引.如果您需要更改位掩码,这将不合适.
>找出一种不使用BIT_COUNT函数进行按位运算的方法.

点击查看更多相关文章