如何加快汉明距离的BIT_COUNT查询速度？

Question

我有一个PHP脚本,用于检查从安全摄像头拍摄的2张静态照片之间的汉明距离.

该表是具有2.4M行的mySQL,由一个Key和4个INT(10)组成.INT(10)已被单独索引,并与Key一起索引,但我没有重要证据表明任何组合比其他组合更快.如果你建议,我可以再试一次.

通过将图像转换为8×16像素来计算汉明权重,并且每四分之一的比特存储在列,pHash0,pHash1 ......等中.

我写了两种方法.第一种方法是使用嵌套的派生表.从理论上讲,每个派生应该检查的数据比它的前身要少.查询是一个准备好的语句,而？字段是我正在检查的文件的pHash [0-3].

Select
    `Key`,
    Bit_Count(T3.pHash3 ^ ?) + T3.BC2 As BC3
  From
    (Select
      *,
      Bit_Count(T2.pHash2 ^ ?) + T2.BC1 As BC2
    From
      (Select
        *,
        Bit_Count(T1.pHash1 ^ ?) + T1.BC0 As BC1
      From
        (Select
          `Key`,
          pHash0,
          pHash1,
          pHash2,
          pHash3,
          Bit_Count(pHash0 ^ ?) As BC0
        From
          files
        Where
          Not pHash0 Is Null And
          Bit_Count(pHash0 ^ ?) < 4) As T1
      Where
        Bit_Count(T1.pHash1 ^ ?) + T1.BC0 < 4) As T2
    Where
      Bit_Count(T2.pHash2 ^ ?) + T2.BC1 < 4) As T3
  Where
    Bit_Count(T3.pHash3 ^ ?) + T3.BC2 < 4

第二种方法更直接.它只是立即完成了所有工作.

Select
    `Key`,
  From
    files
  Where
    Not pHash0 is null AND
    Bit_Count(pHash0 ^ ?) + Bit_Count(pHash1 ^ ?) + Bit_Count(pHash2 ^
    ?) + Bit_Count(pHash3 ^ ?) < 4

第一个查询在大型记录集上更快,而第二个查询在较小的记录集上更快,但在2.4M记录上每个比较都不会超过1-1/3秒.

您是否看到了一种调整此过程以使其更快的方法？可以快速尝试任何建议,例如更改数据类型或索引.

设置为Win7x64,MySQL/5.6.6和InnoDB,nginx/1.99,启用了zend的php-cgi/7.0.0.该脚本从网页调用,并关闭缓冲以立即反馈.

编辑:

如果我将4个32位整数更改为1个二进制(16)可能会更好,这会将比较从4更改为1,但我还必须将我的4个参数转换为128位字符,这个php不会这样做.如果有一种快速的方法来组合它们,它可能会挤出更多的时间.

编辑 接受的答案将速度提高了约500%.我们的假设的快速概要:pHash"A"的bitcount将始终在pHash"B"+/-汉明距离内.

特别感谢@duskwuff的坚韧和耐心.干杯@duskwuff!

编辑 这是我最近的查询:

Select
  files.`Key`, 
  Bit_Count(? ^ pHash0) + Bit_Count(? ^ pHash1) +
  Bit_Count(? ^ pHash2) + Bit_Count(? ^ pHash3) as BC
  From
    files FORCE INDEX (bitcount)
  Where
    bitCount Between ? And ? 
  AND Bit_Count(? ^ pHash0) + Bit_Count(? ^ pHash1) +
  Bit_Count(? ^ pHash2) + Bit_Count(? ^ pHash3) <= ?
  ORDER BY Bit_Count(? ^ pHash0) + Bit_Count(? ^ pHash1) +
  Bit_Count(? ^ pHash2) + Bit_Count(? ^ pHash3)

前4"哪里？" 表示正在检查的文件的4个32位哈希值,接下来的2个"？" 表示该文件的预先计算的bitcount +/-所需的汉明距离,以及最后的"？" 代表汉明的距离.ORDER BY子句仅用于将最接近的匹配项置于顶部,其中LIMIT 1子句将返回最佳匹配项.该bitcount领域有一个B-TREE索引.

来自240万个文件的bitcounts分散成钟形曲线,极端有3或4个,中心有70,000个.如果给出一个bitcount为64的文件(这是最坏的情况),在汉明距离3内查找文件意味着比较20%的文件(在我的情况下为490,000),而寻找汉明距离为0将比较只有2.8%的记录(当然是70,000).

Answer 1

观察到,BIT_COUNT(a ^ b)在下界受之间的差异BIT_COUNT(a)和BIT_COUNT(b).(也就是说,它始终至少等于差异,并且可能更大.)如果您预先计算每一行的总位数,则可以使用它来排除总位数太远的行.你的目标.更好的是,您可以在该列上创建索引,并使用该索引.

我想到的将是以下内容:

ALTER TABLE files ADD COLUMN totalbits INTEGER;
CREATE INDEX totalbits_index ON files (totalbits);

UPDATE files SET totalbits = BIT_COUNT(pHash1) + BIT_COUNT(pHash2)
                           + BIT_COUNT(pHash3) + BIT_COUNT(pHash4);

SELECT `Key` FROM files WHERE (totalbits BETWEEN … AND …) AND …

请注意,有了这个,就不需要将哈希分成四个块.将它们组合成一个列可以使事情变得更容易.