7

次の状況を処理するための効率的な SQL クエリを考え出すのに問題があります。

2 つの列を持つテーブルがあるとします。

groupId : int 
value : float

テーブルが巨大です (数百万行)。「groupId」ごとにさまざまな量の「値」があります。たとえば、100 から 50.000 の間です。すべての float 値は 0 以上ですが、それ以外は無制限です。

特定の groupId に対して、クエリは類似度の降順で並べ替えられた他のすべてのグループを返す必要があります。「類似」は、2 つのグループ内の 30 個の値のすべての可能なペア間の最小ユークリッド距離として定義されます。

類似性のその定義は、私を殺すものです。上記で定義された類似度を計算するには、単純なアルゴリズムは O(n^2) であると思います。現在、「類似性」を再定義するか、上記を効率的に実装するためのアイデアを探しています。PostGis 幾何学的最近傍または最大共通サブシーケンス アルゴリズムのような k 最近傍を含むソリューションを想像できます (ただし、後者の「ファジー」実装が必要なのは、「値」が完全に等しいことはほとんどないためです)。 .

問題が発生した場合に備えて、現在mySQLを使用しています。

乾杯、

Sören
4

4 に答える 4

4

質問が正しかったことを確認できますか？

テーブルは、groupIdによって識別されるベクトルを表します。すべてのベクトルの次元は100から50,000の間ですが、次元に順序は定義されていません。これは、テーブルからのベクトルが実際には同値類の代表であるということです。

ここで、2つの同値類の類似性を、最初の30次元の部分空間に対する同値類の任意の2つの代表の射影の最小ユークリッド距離として定義します。

2次元への投影の例：

A = <1, 2, 3, 4>
B = <5, 6, 7, 8, 9, 10>

Aは、次の同値類のベクトルを表します。

<1, 2, 3, 4>    <2, 1, 2, 3>    <3, 1, 2, 4>    <4, 1, 2, 3>
<1, 2, 4, 4>    <2, 1, 3, 2>    <3, 1, 4, 2>    <4, 1, 3, 2>
<1, 3, 2, 4>    <2, 3, 1, 4>    <3, 2, 1, 4>    <4, 2, 1, 3>
<1, 3, 4, 2>    <2, 3, 4, 1>    <3, 2, 4, 1>    <4, 2, 3, 1>
<1, 4, 2, 2>    <2, 4, 1, 3>    <3, 4, 1, 2>    <4, 3, 1, 2>
<1, 4, 3, 2>    <2, 4, 3, 1>    <3, 4, 2, 1>    <4, 3, 2, 1>

この同値類のすべての代表を最初の2次元に射影すると、次のようになります。

<1, 2>    <1, 3>    <1, 4>
<2, 1>    <2, 3>    <2, 4>
<3, 1>    <3, 2>    <3, 4>
<4, 1>    <4, 2>    <4, 3>

Bは、720個の要素を持つ同値類を表します。最初の2次元への投影により、30個の要素が生成されます。

< 5, 6>    < 5, 7>    < 5, 8>    < 5, 9>    < 5, 10>
< 6, 5>    < 6, 7>    < 6, 8>    < 6, 9>    < 6, 10>
< 7, 5>    < 7, 6>    < 7, 8>    < 7, 9>    < 7, 10>
< 8, 5>    < 8, 6>    < 8, 7>    < 8, 9>    < 8, 10>
< 9, 5>    < 9, 6>    < 9, 7>    < 9, 8>    < 9, 10>
<10, 5>    <10, 6>    <10, 7>    <10, 8>    <10,  9>

したがって、AとBの距離は8の平方根です。これは、投影からの2つのベクトルの最小距離だからです。たとえば、<3、4>と<5、6>はこの距離を生成します。

それで、私は問題の私の理解で正しいですか？

m個の成分を持つn個のベクトルの本当に単純なアルゴリズムは、それぞれ（n-1）の距離を計算する必要があります。距離ごとに、アルゴリズムはmの距離を計算します。/（m-30）！各ベクトルの射影。したがって、100次元（下限）の場合、ベクトルに対して2.65 * 10^32の可能な射影があります。これには、投影間の約7 * 10 ^ 64の距離を計算し、2つのベクトルの距離を見つけるための最小値を見つける必要があります。そして、これをn回繰り返します。

私はあなたを誤解したり、間違えたりしたことを願っています。そうでなければ、これは本当にやりがいのあることと実行不可能なことの間の何かに聞こえます。

私が考えたのは、ベクトルコンポーネントを並べ替えて、それらを一致させようとすることです。マンハッタン距離を使用すると（可能であれば）、ソリューションを簡素化するのに役立つ場合があります。

于 2009-04-06T19:14:22.740 に答える
1

ここにいくつかの良い近似があります：

各グループの重心を計算し、各グループの重心の距離に基づいて比較できます。

それを行う別の方法は、各行の座標をハッシュすることです。同じ場所にハッシュする行は類似していると見なされ、2 つのグループの類似性が更新されます。

次のような詳細情報が役立ちます。

情報は常に更新されていますか? また、更新されている場合はどのくらいの間隔で更新されていますか? どの程度最新で、どの程度正確である必要がありますか?

于 2009-04-07T01:47:44.747 に答える
0

単純なバージョンは次のようになります: (クエリ アナライザーを介して実行されません)

select groupid, min(distance) as mindist
from
   (select other.groupid as groupid,
           min(abs(other.value - us.value)) as distance
    from g us
    join g other on other.groupid != us.groupid
    where us.groupid = ?)
order by mindist
group by groupid

次に、指標を利用するには:

select groupid, min(abs(value - usvalue)) as mindist
from
   (select other.groupid as groupid,
           max(other.value) as value,
           us.value as usvalue
    from g us
    join g other on other.groupid != us.groupid and other.value <= us.value
    where us.groupid = ?

    union

    select other.groupid as groupid,
           min(other.value) as value,
           us.value as usvalue
    from g us
    join g other on other.groupid != us.groupid and other.value >= us.value
    where us.groupid = ?)
order by mindist
group by groupid

これにより、mysql がインデックスを使用して結合の最近傍をすばやく見つけることができるようになるはずです。

これには誤りがあるかもしれませんが、うまくいけば、この考え方が役に立ちます。

于 2009-04-07T02:21:38.533 に答える