5

MySQLデータベースでpHashされた類似画像の検索を改善しようとしています。今、私はこのようにハミング距離を数える pHash を比較します:

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

選択結果(エンジン MyISAM)

  • 20000行; クエリ時間 < 20ms
  • 100000行; クエリ時間 ~ 60ms # 150000 行に達するまではこれで問題ありませんでした
  • 300000行; クエリ時間 ~ 150ms

したがって、クエリ時間の増加は、テーブルの行数に依存します。

また、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に変更しました。この MySQL クエリを PyGreSQL に変換して も成功しません。行 300000 ; クエリ時間 ~ 18 秒

上記のクエリを最適化するソリューションはありますか? 行数に依存しない最適化を意味します。

この問題を解決する方法 (ツール) は限られています。これまでのところ、MySQL が最も単純なソリューションのように見えましたが、専用マシン上の Ruby で動作するすべてのオープン ソース データベース エンジンにコードをデプロイできます。MsSQL https://stackoverflow.com/a/5930944/766217 (テストされていません) の準備ができているソリューションがいくつかあります。誰かが MySQL または PostgreSQL 用に翻訳する方法を知っているかもしれません。

いくつかのコードまたは観察に基づいて回答を投稿してください。stackoverflow.com には、ハミング距離に関する多くの理論的な問題があります。

ありがとう！

4

2 に答える 2

3

アルゴリズムの効率を考えるとき、コンピューター科学者は、 O(何か) で表される順序の概念を使用します。ここで、何かは、計算されるものの数 (この場合は行) の関数です。したがって、時間の経過とともに次のようになります。

  • O(1) - アイテム数に依存しない
  • O(log(n)) - アイテムの対数として増加
  • O(n) - アイテムの割合が増加します (あなたが持っているもの)
  • O(n^2) - アイテムの二乗として増加
  • O(n^3) - など
  • O(2^n) - 指数関数的に増加
  • O(n!) - 数の階乗で増加します

最後の 2 つは、妥当な数の n (80+) に対して事実上計算不能です。

これは大きな n を支配するため、最も重要な項のみが重要であるため、n^2 と 65*n^2+787*n+4656566 は両方とも O(n^2) です。

これは数学的構造であり、アルゴリズムが実際のデータを使用する実際のハードウェア上の実際のソフトウェアでかかる時間は、他のものに大きく影響される可能性があることに注意してください (たとえば、O(n^2) メモリ操作は O( n) ディスク操作)。

あなたの問題では、各行を実行して を計算する必要がありますBIT_COUNT(hash ^ 2028359052535108275) <= 4。これは O(n) 操作です。

これを改善できる唯一の方法は、インデックスを利用することです。これは、B ツリー インデックスの取得が O(log(n)) 操作であるためです。

ただし、列フィールドが関数内に含まれているため、その列のインデックスは使用できません。2 つの可能性があります。

  1. これは SQL サーバー ソリューションであり、MySQL に移植できるかどうかはわかりません。数式を使用してテーブルに永続的な計算列を作成し、BIT_COUNT(hash ^ 2028359052535108275)それにインデックスを配置します。これは、ビット マスクを変更する必要がある場合には適していません。
  2. BIT_COUNT 関数を使用せずにビット演算を実行する方法を考え出します。
于 2013-02-19T03:27:28.010 に答える
2

このソリューションにより、物事が少し速くなりました。ハッシュ比較ごとに派生テーブルを作成し、ハム距離未満の結果のみを返します。この方法では、すでにハムを超えている pHash で BIT_COUNT を実行していません。260 万件のレコードで、約 2.25 秒ですべての一致が返されます。

これは InnoDB であり、インデックスはほとんどありません。

誰かがそれを速くすることができれば、私はあなたに感謝します。

SELECT *, BIT_COUNT(pHash3 ^ 42597524) + BC2 AS BC3 
FROM ( 
    SELECT *, BIT_COUNT(pHash2 ^ 258741369) + BC1 AS BC2 
    FROM ( 
        SELECT *, BIT_COUNT(pHash1 ^ 5678910) + BC0 AS BC1 
        FROM ( 
            SELECT `Key`, pHash0, pHash1, pHash2, pHash3, BIT_COUNT(pHash0 ^ 1234567) as BC0 
            FROM files 
            WHERE  BIT_COUNT(pHash0 ^ 1234567) <= 3 
        ) AS BCQ0 
        WHERE BIT_COUNT(pHash1 ^ 5678910) + BC0 <= 3 
    ) AS BCQ1 
    WHERE BIT_COUNT(pHash2 ^ 258741369) + BC1 <= 3 
    ) AS BCQ2 
WHERE BIT_COUNT(pHash3 ^ 42597524) + BC2 <= 3

これは同等のクエリですが、派生テーブルはありません。返却時間は約3倍。

SELECT `Key`, pHash0, pHash1, pHash2, pHash3 
FROM Files 
WHERE BIT_COUNT(pHash0 ^ 1234567) + BIT_COUNT(pHash1 ^ 5678910) + BIT_COUNT(pHash2 ^ 258741369) + BIT_COUNT(pHash3 ^ 42597524) <=3

最初のハムの値が低いほど、実行が速くなることに注意してください。

于 2014-08-12T20:22:33.507 に答える