0

現在、JSON ファイルに保存されているデータセットがあります。これには、約 40,000 の異なる地理位置情報が含まれています。次のようになります。

[
    {"title": "Place 1", "loc": {"x": "00.000", "y": "00.00000"}},
    {"title": "Place 2", "loc": {"x": "00.000", "y": "00.00000"}},

]

場所locは単なる座標です。

このデータに対してクエリを実行できるようにしたいので、特定のユーザー入力に対して、最も近い場所locを取得できます。n

または言い換えればf、これが機能するようにいくつかの関数を書きたいと思います:

def f(loc, n): ...
f({"x": "5", "y": "5"}, 3) #=> [{"title": "Place 1", "distance": 7.073}, {"title": "Place 2": "distance": 7.073}, {"title": "Place 3", "distance": 7.073}]

場所 1、2、3 がすべて にある場合{x: 0, y: 0}。

このような問題を解決する標準的な方法が何であるかはわかりません。事前計算された距離のインデックスで SQL DB を使用しても機能しませんloc。データベース全体を調べてすべての距離を計算するのは、非効率的で遅すぎます。(30 ミリ秒未満の応答時間が必要です。)

理にかなっている唯一の解決策は、どういうわけか近い場所の「バケツ」を作成し (相互のいくつかrの範囲内で)、次にユーザーが指定した場所とバケットの場所の間の距離を計算して、最初にオプションを絞り込むことです。しかし、そのようなソリューションを自分で作成することは、データベースをまったく使用しないことに似ていると思います。より効率的で業界標準のアプローチが必要です。ありますか？

4

3 に答える 3

0

Oracle は空間データ機能を提供します。あなたのために仕事をする組み込みの最近傍関数SDO_NNがあります。すべてのデータを db に入れるのは傍聴だけで、残りは oracle db によって処理されます。

于 2013-09-22T06:17:48.323 に答える
0

ポイント データ タイプと MySQL のような空間インデックスを持つデータベースを使用できます。quadkey または quadtree を使用することもできます。平面を細分化し、次元を減らします。私の PHP クラス Hilbert-curve@phpclasses.org をダウンロードできます。これはクワッドキーを使用しており、バケット内の場所を整理し、近接検索を構築するのに役立ちます。クワッドキーは、特別なデータベースにより重複する検索を減らすことができます。

于 2013-09-22T06:07:41.473 に答える
0

これは、最近傍問題 (より正式には k-nearest neighbor として知られている) の一般化された形式です。おっしゃる通り、理にかなっているソリューションではバケットを使用します。バケットをデータベースに保存して、SQL を利用できるようにすることができます。適切なバケットにないすべてのポイントを除外するだけです。データベースによっては、これが実際にすでに実装されている場合があります。これは、提案した「業界標準」のアプローチです。

それ以外の場合は、自分で作成することは非常に効率的であり、データベースからあまり逸脱することなく実行できます。

于 2013-09-22T02:32:04.943 に答える