問題タブ [nearest-neighbor]

新しいベクトルが与えられた場合、n個のベクトルの膨大な（数百万）リストがあるとしましょう。セットからかなり近いものを見つける必要がありますが、最も近いものである必要はありません。（最近傍は最も近いものを見つけてn時間で実行されます）

精度を犠牲にして最近傍を非常に迅速に近似できるアルゴリズムはありますか？

編集：おそらく役立つので、データはほとんどの場合非常にスムーズであり、ランダムな次元でのスパイクの可能性はわずかです。

n次元の点のコレクションがあり、どれが最も近いかを見つけたいと思います。私が2次元で思いつくことができる最高のものは次のとおりです。

これは

しかし、これは大きなアレイには遅すぎます。どのような最適化を適用できますか？

関連している：

2つの異なるNumpy配列内のポイント間のユークリッド距離（内ではない）

マップ ポイントをグループにクラスター化する KD ツリーを実装しています。Wikipedia の KD-tree の記事を参考にしています。検索は正しい最近傍点を返しますが、予想よりも遅くなります。これが私のコードです：

私の質問は、「検索ポイントと現在のノードの分割座標の差が、検索ポイントから現在のベストまでの距離 (全体の座標) 未満であるかどうかを単純に比較する」という私の解釈が正しいかどうかです。私はこれを次のように解釈します：

if (fabs(point.coordinate.latitude - self.location.coordinate.latitude) < best.distToPoint)

と

if (fabs(point.coordinate.longitude - self.location.coordinate.longitude) < best.distToPoint)

それぞれ。その他アドバイスも大歓迎です。

ありがとう。

ポイントの配列を入力として取り、配列内の各ポイントについて、それ自体以外の最も近いポイントを見つけるメソッドを作成しています。私は現在、力ずくでこれを行っています（すべてのポイントを他のすべてのポイントでチェックしています）。私の現在の実装では配列がソートされていませんが、CompareByX メソッドを使用して px 値でソートできます。アルゴリズムの実行時間をチェックしていますが、n の値が大きいと非常に時間がかかります。私はこのテーマについてあまり知識がなく、さまざまなタイプのデータ構造についてほとんど知りません。簡単な助けがあれば素晴らしいでしょう!

私の現在のコードは次のとおりです。

たとえば、座標があります。

OSMDBで最も近いノードを見つけたい

この例では、ノード906459460

http://www.openstreetmap.org/api/0.6/node/906459460

次に、どの方法がその一部であるかを知りたい

この例では

http://www.openstreetmap.org/api/0.6/way/78456451

http://www.openstreetmap.org/api/0.6/way/76966153

http://www.openstreetmap.org/api/0.6/way/76965957

APIを使用するにはどうすればよいですか？ありがとう

OpenCL を使用して、2 組の 3D ポイント間の最近傍を見つけています。

Nearest Neighbour: DataSet 内の各ポイント (x、y、z) について、モデル内で最も近いものを見つける必要があります。二乗距離 = (Ax-Bx)^2 + (Ay-By)^2 + (Az-Bz)^2

ここで私がこれまでに行ったこと：

コードは機能しているように見えますが、最適化できると確信しています。ローカルメモリを利用して改善する方法を知りたいです。

ありがとう

PS kd-tree のように、最も近い隣人を見つけるための他の (より良い) 方法があることは知っていますが、今のところ、簡単な方法を実行したいと思います。

現在使用されている双三次の方法ではなく、最近隣のサイズ変更で画像をレンダリングする必要があります。現在、次のものを使用しています。

これは IE と Firefox では機能しますが、Chrome と Safari では機能しません。この効果を達成するための Webkit の代替手段やその他の方法はありますか?

(ツリー上に) 再帰関数があり、再帰を使用せずにツリーを暗黙的なデータ構造 (配列) として表現する必要があります。

関数は次のとおりです。

このプロパティを使用して、ツリーを配列として表しています。

これは私がやったことです：

最後のステップは再帰を取り除くことですが、方法が見つかりません。ヒントはありますか? ありがとう

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

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

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

どういうわけか、以下のアップスケールされたスプライト画像は、InternetExplorer9では鮮明な最近傍のピクセルパーフェクトとして表示されません。FFでは完全にピクセルパーフェクト/鮮明に動作します。

ただし、IEでは、バイキュービックがスムーズになるようです。この場合は、これは望ましくありません。このCSSの何が問題になっているのでしょうか。