問題タブ [nearest-neighbor]

3-dの点は、（x、y、z）によって定義されます。任意の2点（X、Y、Z）と（x、y、z）の間の距離dは、d = Sqrt [（Xx）^ 2 +（Yy）^ 2 +（Zz）^2]です。現在、ファイルには100万のエントリがあり、各エントリは特定の順序ではなく、空間内のあるポイントです。任意のポイント（a、b、c）が与えられた場合、それに最も近い10ポイントを見つけます。百万ポイントをどのように保存し、そのデータ構造からそれらの10ポイントをどのように取得しますか。

2 次元データ (マップ上のポイント) でいっぱいのデータベースがあります。各レコードには、ジオメトリ タイプのフィールドがあります。私ができる必要があるのは、k 個の最も近いポイントを返すストアド プロシージャにポイントを渡すことです (k は sproc にも渡されますが、それは簡単です)。http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspxで単一の最近傍を取得するクエリを見つけましたが、それを拡張する方法がわかりませんk最近隣人を見つけます。

これは現在のクエリTです。 はテーブル、gはジオメトリ フィールド、@xは検索対象のポイント、Numbersは整数 1 ～nのテーブルです。

内側のクエリは最も近い空でない領域を選択し、外側のクエリはその領域から上位の結果を選択します。外側のクエリは (eg) に簡単に変更できますがSELECT TOP(20)、最も近いリージョンに結果が 1 つしか含まれていない場合は、それで行き詰まります。

おそらく、 k 個のレコードを含む最初の領域を再帰的に検索する必要があると思いますが、テーブル変数を使用しないでください (テーブル構造を作成する必要があり、変更されやすいため、メンテナンスの問題が発生します。多くのフィールドがあります)。方法がわかりません。

現在、バランスの取れた KD ツリー(K=2)のすべてのノードの K Nearest Neighborを見つけようとしています。

私の実装は、ウィキペディアの記事のコードのバリエーションであり、任意のノードO(log N)の KNN を見つけるのはかなり高速です。

問題は、各ノードの KNN を見つける必要があるという事実にあります。 各ノードを反復処理して検索を実行すると、約 O(N log N) になります。

これを行うより効率的な方法はありますか？

私はレシピのコレクションを持っており、それぞれにいくつかの材料があります。この情報は結合テーブルに格納されます。レシピを教えてください、材料に基づいてそれに似たレシピを見つけたいです。どうすればこれを行うことができますか？

2 つの類似した画像内の特定のキーポイント間の一致を見つけるための最近傍アルゴリズムの実装に出会いました。キーポイントは、SIFT アルゴリズムによって生成されました。ポイントは 128 次元のベクトルで記述され、両方の画像にそのようなポイントが多数あります。

マッチング アルゴリズムは最近傍検索を使用し、1 つのイメージ内の各ポイントに対して、もう 1 つのイメージ内の対応する最も近いポイントを計算します。「近さ」は、ポイントのベクトル間の最小ユークリッド距離によって表されます。そのような最良の一致は、距離が特定のしきい値を下回るポイントのペアのみを取得することによって選択されます。

しかし、私が遭遇した実装では、一方の画像のキーポイントのすべてのベクトルをもう一方の画像のベクトルと乗算し、積の行列を形成します。次に、積が所定のしきい値よりも高い点を見つけます。

この実装は正しい結果をもたらしますが、それがどのように機能するか知りたいです。ベクトル間の相関をメトリックとして使用しますか、それともここで何か他のことが起こっていますか?

last.fmの近所の人と同じように、似たようなお気に入りの映画/本/興味などを持つユーザーを見つけることができるシステムを作成しようとしています。最も相互利益を共有しているユーザーは、最も一致度が高く、ユーザープロファイルに表示されます（5つ程度の最適一致）。

これを行うための合理的に速い方法はありますか？明らかな解決策は、ユーザーIDとインタレストIDを使用してテーブルを作成し、ユーザーを他のすべてのユーザーと比較することですが、それは、それぞれ20のインタレストを持つ100万人のユーザーがいるテーブルでは永遠にかかります。

last.fmは非常にうまく機能しているので、いくつかの効率的な解決策が存在すると思います。mySQLやpgSQLなどの一般的なSQLデータベースを使用することをお勧めしますが、何でもかまいません。

あなたの提案をありがとう。

更新：結局のところ
、最大の問題はSQLデータベースで最も近いネイバーを見つけることです。オープンソースのものはどれもこの種の検索をサポートしていないからです。
したがって、私の解決策は、サービスとして実行するようにANNを変更し、PHPからクエリを実行することです（たとえば、ソケットを使用）。たとえば、メモリに7次元のユーザーが何百万人もいることはそれほど大きな問題ではなく、信じられないほど高速に実行されます。

小さなデータセットの別の解決策は、この単純なクエリです。

20〜50ミリ秒、10万人のユーザーがそれぞれ平均で約20の関心（10000の可能な関心のうち）を持っている

以前の質問に答えてくれて、ここまでたどり着いてくれた人たちに感謝します。

約 25,000 個のベクトルのテーブルがあり、それぞれが 48 次元で、値の範囲は 0 ～ 255 です。

近傍点または最近傍点を見つけるための Locality Sensitive Hash ( http://en.wikipedia.org/wiki/Locality-sensitive_hashing ) アルゴリズムを開発しようとしています。

私の現在のLSH関数はこれです：

この時点での私の質問は次のとおりです。

A:コードの「normalvariate(10, 4)」部分に最適な値はありますか。これは、random.normalvariate ( http://docs.python.org/library/random.html#random.normalvariate ) 関数に組み込まれた python であり、「安定した分布から独立して選択されたエントリを持つ d 次元ベクトル」を生成するために使用しています。 . 私の実験から、値はあまり重要ではないようです。

B:ウィキペディアの記事の上部には、次のように記載されています。

d(p,q) <= R の場合、少なくとも P1 の確率で h(p) = h(q)

d(p,q) >= cR の場合、h(p) = h(q) で確率は最大 P2

ここで言及されている R 値は、安定分布セクションで言及されている R 値でもありますか。( http://en.wikipedia.org/wiki/Locality-sensitive_hashing#Stable_distributions )

C:前の質問 (B) に関連しています。hasing 関数でより高い値の R を使用すると、ベクトルがより狭い範囲のハッシュ値にマップされることがわかりました。R 値を最適化する方法はありますか。

D:およそいくつのテーブルを使用できますか?

スプライトシートを使用してアニメーション化するスプライトがあります。彼はたった16x16ですが、私は彼をすべてのピクセルの良さで約64x64にスケールアップしたいと思います！

結果はひどいです、もちろんブラウザはそれをアンチエイリアシングしています。：/

ありがとう！

編集：cssは必要ありません、これが私の描画関数です。

ここでちょっと動作しているのを見てください（codepen）

2次元空間内の点のセットSが与えられた場合、セット内の各点の最近傍（ユークリッド）を計算するアルゴリズムを提供します。最隣グラフと呼ばれていると思いますよね？既存の効率的なアルゴリズム（N log N）、ここでN = len（S）？

あなたの場所に応じて最も近いレストランを提供するアプリを構築したいと思います。レストランに対応するすべての POI を含むデータベースを用意し、携帯電話の GPS を使用して位置情報を取得します...

どのアルゴリズムが適切でしょうか? それについての良いドキュメントはどこにありますか?

ありがとう