加速MySQL中的多维欧几里德距离计算

Question

我有下表存储有关图像的数据:

images
 - id (int)
 - sample_1_1 (int)
 - sample_1_2 (int)
 - sample_1_3 (int)
 - sample_2_1 (int)
 - sample_2_2 (int)
 - sample_2_3 (int)
 - ... # Up until sample_25_3

任务是计算收集的数据之间的距离.目前,我正在使用75维(正确的,3*25 = 75)欧几里德距离计算编程为数据库中的存储过程:

CREATE DEFINER=`root`@`localhost`
FUNCTION `distanceBetween`(compareId INT, toId INT) RETURNS double
    READS SQL DATA
    DETERMINISTIC
BEGIN
 DECLARE distance DOUBLE;
SELECT euclidDistance(
 i1.sample_1_1, i1.sample_1_2, i1.sample_1_3,
 i2.sample_1_1, i2.sample_1_2, i2.sample_1_3,
 ...
 ) INTO distance
FROM images i1, (SELECT * FROM images WHERE id = toId) i2
WHERE i1.id = compareId;
RETURN distance;
END

用另一个子程序计算2 75-dim之间的实际距离.向量:

CREATE DEFINER=`root`@`localhost`
    FUNCTION `euclidDistance`(
 img1_sample1_1 INT, img1_sample1_2 INT, img1_sample1_3 INT,
 img2_sample1_1 INT, img2_sample1_2 INT, img2_sample1_3 INT,
 ...
 ) RETURNS double
RETURN SQRT(
   quadDiff(img1_sample1_1, img2_sample1_1)
 + quadDiff(img1_sample1_2, img2_sample1_2)
 + quadDiff(img1_sample1_3, img2_sample1_3)
 + ...
)

另一个子程序来计算两个值之间的平方差:

CREATE DEFINER=`root`@`localhost`
FUNCTION `quadDiff`(var1 INT, var2 INT) RETURNS int(11)
RETURN POW(var1 - var2, 2)

函数本身非常精细,并返回确定性结果,这些结果在数学上和逻辑上都是正确的.

当我想要将"最接近"的图像传送到给定图像时,问题出现了 - 这意味着与任何给定图像的距离最小的图像.为此,我使用另一个程序:

CREATE DEFINER=`root`@`localhost`
PROCEDURE `getSimilarImages`(imageId INT, `limit` INT)
BEGIN
    SELECT i2.id, i2.filename, distanceBetween(i1.id, i2.id) distance
    FROM images i1, (SELECT * FROM images WHERE id != imageId AND duplicateImageId IS NULL) i2
    WHERE i1.id = imageId
    ORDER BY distance
    LIMIT 10;
END

该数据库目前有大约30.000张图像.这意味着完成CALL getSimilarImages(123, 10);大约需要12秒.对于任何应用程序来说,这都太长了,无论是基于Web还是基于应用程序.

所以,我想加快速度.我有什么选择？您是否认为有可能优化图像比较或计算距离的过程？

我想过缓存程序的结果,但我不知道如何这样做.我还可以在添加新图像时将每个图像与每个其他图像进行比较,但这会使图像添加一个非常长的过程,这也是不可接受的.

如果它有帮助,我可以提供有关系统设置的更多信息,但我感谢您提供的任何指示.目前的情况并不好,我真的需要做点什么,因为图像数据库只会随着系统每小时的增长而增长.

Answer 1

正如您所发现的，您的 ORDER BY distance(a,b) 操作正在计算大量 75 维距离，并且毫不奇怪，它需要很长时间。它必须计算全部数据，以便可以执行 ORDER 操作。哎哟。

以下是有关欧几里得距离的观察结果，可能会对您有所帮助：边界框是一个有用的近似值。当您使用 GetSimilarImages 时，是否可以仅包含与您正在使用的 imageId 的特定阈值距离内的图像？

假设您只关心radimageId 范围内的图像。然后您可以像这样重新设计 GetSimilarImages 查询。

PROCEDURE `getSimilarImages`(imageId INT, `limit` INT, rad INT)
BEGIN
    SELECT i2.id, i2.filename, distanceBetween(i1.id, i2.id) distance
    FROM images i1, 
    (SELECT * FROM images WHERE id != imageId AND duplicateImageId IS NULL) i2
    WHERE i1.id = imageId
      AND i1.img_sample_1_1 BETWEEN i2.img_sample_1_1 - rad
                                AND i2.img_sample_1_1 + rad
      AND i1.img_sample_1_2 BETWEEN i2.img_sample_1_2 - rad
                                AND i2.img_sample_1_2 + rad
      AND i1.img_sample_1_3 BETWEEN i2.img_sample_1_3 - rad
                                AND i2.img_sample_1_3 + rad
    ORDER BY distance
    LIMIT 10;
END

在此示例代码中，我任意选择了 75 个维度中的前三个用于边界框包含代码（三个BETWEEN子句）。为了使此优化发挥作用，您需要至少在某些用于边界框包含的维度上创建索引。

选择三个维度或选择任何特定维度没有什么特别的。如果您从数据中知道某些尺寸可以更好地区分图像，那么就可以选择这些尺寸。您可以根据需要选择任意多个尺寸。但是，当然存在索引开销。