node.js - 場所と指定された半径に基づいてデータを取得する

Question

シナリオ：大きなデータセットがあり、各エントリに場所（x、y-座標）が含まれています。このデータセット内の100m以内にあるこのデータセットからすべてのエントリを要求し、配列として返すことができるようにしたいと思います。

このようなものを実装するにはどうすればよいですか？推奨されるパターンやフレームワークはありますか？以前は、リレーショナルまたは単純なKey-Valueタイプのデータのみを扱ってきました。

Answer 1

この問題を効率的に解決するデータ構造はkdツリーです。node.jsモジュールを含む、利用可能な多くの実装があります。

Answer 2

データ セットを PostgreSQL に配置し、R ツリー インデックスを使用します。その後、バウンディング ボックス クエリを実行して、任意の場所の +-100 マイルのすべてのポイントを取得できます。次に、半径距離を計算し、100 マイル以内のポイントを受け入れます。独自のスキーマとクエリを展開するか、PostGIS を使用できます。

R ツリーとは異なり、KD ツリーは本質的にバランスが取れていません。そのため、KD ツリーの構築方法によっては、不均衡なツリーと最長のパスが原因で、一貫性のないパフォーマンスが得られる可能性があります。