5

約 500 万行のテーブルがあり、各行には 10 個のディメンションを表す 10 個の列があります。新しい入力がテーブル内で検索を実行し、マンハッタン距離を使用して最も近い行を返すようになったときにできるようにしたいと考えています。距離は abs(Ai-Aj)+abs(Bi-Bj) の合計です...問題は、クエリを実行すると、テーブル全体のフルスキャンが実行され、距離が計算されることです。すべての行を並べ替えて、上位の X を見つけます。

プロセスを高速化し、クエリをより効率的にする方法はありますか?

SDO_GEOMETRY の距離関数をオンラインで調べましたが、4 次元を超えるものは見つかりませんでした。

ありがとうございました

4

2 に答える 2

2

ポイントAを挿入していて、半径rの近傍内にあるポイントを検索する場合(つまり、任意のメトリックでr未満の距離)、非常に単純なクエリを実行できます。

select x1, x2, ..., xn
from   points
where  x1 between a1 - r and a1 + r
and    x2 between a2 - r and a2 + r
...
and    xn between an - r and an + r

...どこでA = (a1, a2, ..., an)、境界を見つけるため。のすべてのx1, ...,xnフィールドにインデックスがある場合points、このクエリはフル スキャンを必要としません。現在、この結果には近傍の外側にあるポイント (つまり、コーナーのビット) が含まれている可能性がありますが、適切なサブセットを見つけるのは簡単です。すべてのポイントに対してチェックするのではなく、このサブクエリでレコードに対してチェックできるようになりました。あなたのテーブルで。

このクエリをさらに絞り込むことができる場合があります。これは、マンハッタン メトリックを使用すると、近傍が正方形になり (上記に対して 45 度ですが)、正方形は比較的扱いやすいためです。(10 次元でも。)ただし、必要なより複雑なロジックは、最終的には最適化よりもオーバーヘッドになる可能性があります。

于 2013-01-25T11:00:49.043 に答える
0

関数ベースの indexを使用することをお勧めします。この距離を計算する必要があるため、関数ベースのインデックスを使用して事前に計算します。

次の質問を読みたいと思うかもしれません。それはリンクしています。関数ベースのインデックスは、非表示の列を作成します。この非表示の列には manhanttan 距離が保持されるため、並べ替えが容易になります。

@Xophmeister のコメントをありがとう。関数ベースのインデックスは、任意のポイントには役立ちません。ここで役立つSQL関数がわかりません。ただし、機械学習データ マイニング アルゴリズムを使用する意思がある場合。

k-means clusteringを使用して 500 万行をクラスター化することをお勧めします。あなたが見つけた1000個のクラスターセンターとしましょう。このクラスターの中心を別のテーブルに置きます。クラスタリングの定義により、ポイントはクラスタ センターに割り当てられます。このため、どのポイントがこのクラスターの中心に最も近いかがわかります。たとえば、クラスター (1) には 20.000 ポイントが含まれ、... クラスター ( 987) には 10.000 ポイントが含まれます ...

任意のポイントは、1 つのクラスターに近くなります。ポイントがクラスター 987 に最も近いことがわかります。このクラスターの中心に属するポイント (10.000 ポイント) のみを使用して、SQL を実行します。

これを有効にするには、スキーマにいくつかのテーブル/列を追加する必要があります。5.000.000 行が継続的に変化する場合は、変化するたびに k-means クラスタリングを再度実行する必要があります。ただし、それらがかなり一定の値である場合は、1 週間または 1 か月に 1 回のクラスタリングで十分です。

于 2013-01-25T09:55:48.237 に答える