1

選択した ID を持つポイントに最も近い k 個のポイントを取得する手順を構築しようとしています。sdo_geometry や nn などの空間ロケーター機能を使用せずにこれを行う必要があります。

基本的に私はオラクルにID、Data_X、Data_Yのテーブルを持っています。テーブルに 10 個のエントリがあり、架空の点 target_x、target_y に最も近い 3 つの点が必要だとします。

与えられた架空の点を使用して、テーブル内の各点のユークリッド距離を計算する必要があります。最も近い隣人のIDを返すpl/sqlのアルゴリズムを知りません。

4

2 に答える 2

3

各ポイントと選択したポイント間の距離 (ピタゴラス) を計算し、距離で並べ替えます。疑似 SQL:

select id from points
order by sqrt(sqr(Data_x - target_x) + sqr(Data_y - target_y))

最初の 3 行は最も近い 3 点です。

于 2011-04-04T12:38:34.937 に答える
2

ナンの答えは素晴らしい出発点です。それがうまくいくなら、私はそれを使用します。残念ながら、ほとんどの場合、完全なテーブル スキャン (または、カバー インデックスがある場合は完全なインデックス スキャン) が必要になります。

パフォーマンスが問題になる場合は、おそらく、データに対して貧弱な空間インデックスを作成することを検討できます。「インデックスの作成」ほど単純ではありませんが、うまくいくかもしれません。

適切な方法は、カスタム インデックスを作成することですが、それは sdo_geometry ホイールを再発明するだけであり、回避したいとおっしゃっていました。

単純だが大雑把な方法 (免責事項: これは私の思いつきであり、テストされていません) は、2D 空間内のすべてのポイントを正方形のブロックにグループ化する関数ベースのインデックスを作成することです。基本的に、各 (x,y) ペアをブロックのリストにマップするためのインデックスを作成します。各ブロックには定義された幅と高さがあり、検索を行うには、最初にどのブロックのグリッドを検索する必要があるかを判断し、次にそのグリッド内のポイントのリストだけをクエリします。

インデックスの例は次のようになります。

CREATE INDEX grid_block_i ON points (TRUNC(Data_X/100), TRUNC(Data_Y/100), id);

100 をどの値に置き換えるかは、ポイントが取る値の範囲によって異なります。平面を多数のグリッド ブロックに分割して、インデックスが適切に選択されるようにする必要があります。ただし、典型的なクエリでは、候補を見つけるためにあまりにも多くのブロックを検索する必要があるほど大きくはありません。

次のようなクエリを使用して、上記のインデックスを使用できます。

select id
from (select id, Data_X, Data_Y
      from points
      where TRUNC(Data_X/100) BETWEEN TRUNC(:target_x/100)) - :threshold
                                  AND TRUNC(:target_x/100)) + :threshold
      and   TRUNC(Data_Y/100) BETWEEN TRUNC(:target_y/100)) - :threshold
                                  AND TRUNC(:target_y/100)) + :threshold
     )
order by sqrt(sqr(Data_x - :target_x) + sqr(Data_y - :target_y))

次に、:threshold を設定して、クエリから点のブロックの大きなセットを基本的に除外できます。機能インデックス (つまり 100) の値としきい値が正しく設定されている場合、クエリが関数ベースのインデックスを使用して候補の小さなセットを取得することがわかります。テーブル。

欠点は、:threshold が低すぎる場合、クエリが行を返さない可能性があることです。一方、ニーズによっては、これは便利な機能になる場合があります。

于 2011-04-04T13:55:52.337 に答える