4

最も近い場所 (緯度/経度で表される) を O(n) 時間よりも早く計算するアルゴリズムがあるかどうか疑問に思っています。

Haversine 式を使用して基準点から各場所までの距離を取得し、ASC を並べ替えることができることはわかっていますが、これは大規模なデータ セットには非効率的です。

MySQL DISTANCE() 関数はどのように機能しますか? 私はO(n)を推測していますか?

4

10 に答える 10

8

ポイントを格納するためにkd ツリーを使用する場合は、O(log n)時間内 (予想される) またはO(sqrt(n))最悪の場合にこれを行うことができます。

于 2009-07-29T03:35:05.630 に答える
2

グリッド(私はそれを象限と呼んでいます)を使用して、数年前にDDJで最も近いラインを見つけることについての記事を書きました。(線の代わりに)最も近い点を見つけるためにそれを使用することは、それを単に減らすことになるでしょう。

象限を使用すると、時間を大幅に短縮できますが、複雑さを数学的に決定することはできません(理論的には、すべてのポイントが1つの象限にある可能性があります)。象限/グリッドを使用するための前提条件は、検索するポイントの最大距離があることです。最大距離を指定せずに、最も近いポイントを探すだけでは、象限を使用できません。

この場合、O(log n)の検索の複雑さを持つ、最近傍問題のテンプレート(DDJのLarry Andrews)を見てください。両方のアルゴリズムの実行時間を比較しませんでした。おそらく、妥当な最大幅がある場合は、象限の方が適しています。より優れた汎用アルゴリズムは、LarryAndrewsのアルゴリズムです。

于 2009-07-29T08:55:27.683 に答える
2

検索対象のデータ セットが静的な場合 (たとえば、米国内のすべてのガソリン スタンドの座標など)、適切なインデックス (BSP) を使用すると効率的な検索が可能になります。Postgres は 90 年代半ば以降、2 次元のインデックス付きデータを適切にサポートしているため、この種のクエリを実行できます。

于 2009-07-29T03:34:09.127 に答える
2

MySql について言及されていますが、SQL Server 2008には地理データ型を含むかなり洗練された空間機能がいくつかあります。あなたが求めている種類のことを行うことについて、いくつかの情報があります。パフォーマンスについて話すほど、私は空間をよく知りません。しかし、あなたが求めていることを実行するための時間制限アルゴリズムがあるとは思えませんが、場所に対して高速なセット操作を実行できる可能性があります。

于 2009-07-29T03:16:07.447 に答える
2

O(n)より良い?基数ソートの方法を使用するか、場所の一般的な場所を表すハッシュキーを使用して場所を保存する場合のみ。

たとえば、地球を緯度と経度で分単位で分割し、結果の領域を列挙し、その領域の場所のハッシュを作成できます。そのため、最も近い場所を取得するときは、最大で 9 つのハッシュ キーを確認するだけで済みます。隣接するグリッドがこれまでに見つかった最良の場所よりも近い場所を提供できるかどうかを事前にテストして、場所のセットを減らすことができます。までの距離を計算します。それはまだ O(n) ですが、定数係数ははるかに小さくなっています。適切に実装されていれば、気付かないことさえあります。

または、データがメモリ内にある場合、またはランダムにアクセスできる場合は、緯度と経度の両方で並べ替えて保存できます。次に、バイナリ検索を使用して、それぞれのデータ セットで最も近い緯度と経度を見つけます。次に、より近い場所を見つけることができなくなるまで、緯度または経度が増加する場所 (つまり、前後の場所) を読み取り続けます。

緯度で並べ替えられたデータのいずれかの側にある次の場所の緯度が、これまでに見つかった最良のケースよりも近くない場合、それらが元のポイントと同じ経度に属していたとしても、近い場所を見つけることができないことがわかります。どの距離が計算されているか。経度でソートされたデータにも同様のテストが適用されます。

これは実際にはO(n)よりも優れています-O(logN)に近いと思いますが、データへのシーケンシャルではなくランダムなアクセスと、すべてのデータ(または少なくともデータへのキー)の複製が必要です)。

于 2009-07-29T03:09:19.737 に答える
1

私自身は見ていませんが、PostgresにはGISデータの管理専用のモジュールがあります。

私が前世で取り組んだアプリケーションでは、すべてのデータを取得し、クアッドツリー(2Dスペースの場合)またはオクトツリー(3Dスペースの場合)のキーを計算して、データベースに保存しました。その後、データベースから値をロードし(クアッドツリーを再計算する必要がないようにするため)、標準のクアッドツリー検索アルゴリズムに従うという単純な問題でした。

もちろん、これは、データ構造に取り込むために、少なくとも1回はすべてのデータに触れることを意味します。しかし、このデータ構造を維持することは、それ以降、より良いルックアップ速度を得ることができることを意味します。データセットごとに最近傍チェックをたくさん行うと思います。

(kd-treeのウィキペディアには良い説明があります:http://en.wikipedia.org/wiki/Kd-tree

于 2009-07-29T04:24:08.727 に答える
1

空間インデックスが必要です。幸いなことに、MySQL はSpatial Extensionsでまさにそのようなインデックスを提供します。彼らは内部で R ツリー インデックスを使用しますが、何を使用するかは問題ではありません。上記のマニュアルページには、多くの詳細が記載されています。

于 2009-07-29T08:29:27.767 に答える
1

(1) 最も近い場所を探している場合は、並べ替える必要はありません。リストを反復処理して、各ポイントまでの距離を計算し、最も近いポイントを追跡します。リストを完了するまでに、答えが得られます。

さらに良いのは、グリッドの概念を導入することです。各ポイントをグリッドに割り当てます。次に、検索のために、まず現在のグリッドを決定し、グリッド内のポイントで計算を実行します。ただし、少し注意が必要です。テスト場所がグリッドの境界に近い場合は、それらのグリッドも検索する必要があります。それでも、これは非常にパフォーマンスが高い可能性があります。

于 2009-07-29T03:14:20.943 に答える
0

R ツリー インデックスを使用すると、このような空間検索を高速化できます。作成されると、そのような検索は O(n) よりも優れたものになります。

于 2009-07-29T03:52:05.970 に答える
0

これを行うのに十分な大きさのテーブルがあれば、理論的にはそれを行うことができると思います...第二に、おそらく正しくキャッシュすると、非常に良い平均的なケースが得られるでしょうか?

于 2009-07-29T03:10:17.503 に答える