6

画像に関するデータを保存する次の表があります。

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

別のサブルーチンを使用して、275-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)
 + ...
)

そして、2つの値の差の2乗を計算する別のサブルーチン：

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枚の画像が含まれています。これは、aが終了するのCALL getSimilarImages(123, 10);に約12秒かかることを意味します。これは、Webベースであろうとアプリケーションベースであろうと、どのアプリケーションにとっても長すぎます。

だから、私は物事をスピードアップしたいと思います。私のオプションは何ですか？距離を比較または計算する画像のプロセスを最適化する可能性はありますか？

手順の結果をキャッシュすることを考えましたが、その方法がわかりません。新しい画像が追加されるとすぐに、すべての画像を他のすべての画像と比較することもできますが、それでは画像が非常に長いプロセスで追加されるため、これも受け入れられません。

役立つ場合は、システムセットアップに関する詳細情報を提供できますが、ご提供いただけるアドバイスをいただければ幸いです。現在の状況は良くなく、私は本当に何かをする必要があります。なぜなら、イメージデータベースはシステムが稼働する時間ごとにしか大きくならないからです。

4

3 に答える 3

4

ご存知のように、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

このサンプルコードでは、バウンディングボックスインクルージョンコード（3つのBETWEEN句）に使用する75のディメンションの最初の3つを任意に選択しました。この最適化を機能させるには、バウンディングボックスの包含に使用されるディメンションの少なくとも一部にインデックスを作成する必要があります。

3次元を選択すること、または特定の次元を選択することについて特別なことは何もありません。データから、特定の寸法が画像をよりよく区別することがわかっている場合は、それらを選択します。必要な数のディメンションを選択できます。ただし、もちろん、インデックス作成のオーバーヘッドがあります。

于 2012-08-03T11:16:11.920 に答える
1

UDF C 関数をコーディングするか、GPU 関数を呼び出すネイティブ C 関数を呼び出します。

于 2012-08-03T12:52:02.053 に答える
0

この場合の最適化のヒント:

列にインデックスを追加しid、duplicateImageId望ましい a clustured index.

巨大なテーブルで複数選択を避けるようにしてくださいimages。

関数内で関数を呼び出しているため、関数呼び出しの数を減らすことで、パフォーマンスをわずかに向上させることができます。これらの関数呼び出しはすべて、ハードウェア リソースを消費するメモリ スタックで維持する必要があります。

最適化のためにコードを変更するたびに、パフォーマンスのベンチマークを行います。

CREATE PROCEDURE getSimilarImages(imageId INT unsigned, limit INT unsigned)
BEGIN
    SELECT i2.id, i2.filename, 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,
 ...
 ) AS distance
    FROM images i1, (SELECT id, filename 
                     FROM images 
                     WHERE id <> imageId AND 
                           duplicateImageId IS NULL
                    ) i2
    WHERE i1.id = imageId
    ORDER BY distance
    LIMIT 10;
END;

CREATE 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(
   POW(img1_sample1_1 - img2_sample1_1, 2)
 + POW(img1_sample1_2 - img2_sample1_2, 2)
 + POW(img1_sample1_3 - img2_sample1_3, 2)
 + ...
);

お役に立てれば。

于 2012-08-03T09:56:35.563 に答える