Ускорение вычисления многомерного -евклидового расстояния в MySQL

У меня есть следующая таблица, в которой хранятся данные об изображениях:

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 -дим. векторы:

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 секунд. Это слишком долго для любого приложения, будь то веб-приложение или приложение.

Итак, я хочу ускорить процесс. Каковы мои варианты? Видите ли вы какой-либо потенциал для оптимизации процесса сравнения изображений или расчета расстояний?

Я думал о кэшировании результата процедуры, но понятия не имею, как это сделать. Я также мог бы сравнивать каждое изображение с каждым другим изображением, как только добавляются новые изображения, но это будет очень долгим процессом добавления изображений, что также неприемлемо.

Я могу предоставить больше информации о настройке системы, если это поможет,но я ценю любые указатели, которые вы можете предоставить. Текущая ситуация нехорошая, и мне действительно нужно что-то делать, потому что база данных изображений будет только расти с каждым часом работы системы.

6
задан F.P 3 August 2012 в 11:51
поделиться