問題タブ [nearest-neighbor]

3D の数千点のコレクションが与えられた場合、あるカットオフ値 (ユークリッド距離に関して) 内に収まる各粒子の近傍のリストを取得する必要があり、可能であれば、最も近いものから最も遠いものへと並べ替える必要があります。

CUDA または OpenCL 言語で、この目的のための最速の GPU アルゴリズムはどれですか?

Linux ですべてのネットワーク ネイバーを検出する必要があり (Linux も実行されています)、それらの IP アドレスを取得する必要があります (第 3 層)。それを行う方法はありますか？

ところで、私はCでなく、でそれを行う必要がありますshell

よろしくお願いします！

ソートされたマップから、指定された値 vの前にm個のエントリを開始して、 n個のエントリのサブセットを取得したいと思います。たとえば、キーセットk = {0.2、0.3、0.4、0.6、0.8、0.9、1.0}の場合、n = 5、m = 2、v = 0.5のクエリは、{0.3、0.4、0.6、0.8を返します。 、0.9}。（大きな）セット全体を反復処理することなく、そのようなクエリをサポートするJavaのデータ構造の実装はありますか？

これは何のために必要ですか？補間。マップ内の値に基づいてvで補間したいと思います。しかし、私は多くのvを持っています。それらはソートされており、それらの間の間隔はkの間隔よりもはるかに小さくなっています。そこで、マップからエントリの範囲を取得し、それらを使用して高価な準備計算を実行し（たとえば、多項式の係数を計算し）、その範囲内の別の値をすばやく補間できます（その値で多項式を評価することにより）。

しかし、なぜvの前にm個のエントリが必要なのですか？kの値は通常等間隔であり、補間間隔の終わりでの高振動のルンゲ現象を回避するために、単純にそれらを切り取ります。つまり、補間の実際の有効な間隔の前にいくつかのノードが必要です。

それは理にかなっていますか？あなたの提案は何ですか？

（java.util.TreeMap.ceilingEntry（）のようなメソッドがイテレーターを返し、それを使用して2回戻ることができれば楽しいでしょう。）

立方体の箱の中に、R^3に大きな収集ポイントがあります。各点のk最近傍を見つけたいと思います。通常はkd木のようなものを使うと思いますが、この場合は周期境界条件があります。私が理解しているように、kdツリーは、スペースを1次元少ないハイパープレーンに分割して分割することで機能します。つまり、3Dでは、2Dプレーンを描画してスペースを分割します。任意のポイントについて、それは平面上、その上、またはその下のいずれかにあります。ただし、周期境界条件で空間を分割すると、点はどちらかの側にあると見なされる可能性があります。

R ^ 3の周期境界条件を持つ最近傍のリストを見つけて維持する最も効率的な方法は何ですか？

近似は十分ではなく、ポイントは一度に1つだけ移動します（N体シミュレーションではなくモンテカルロを考えてください）。

here で説明されているように、いくつかの植毛シミュレーションを行いたいです。

このために、各 2D ポイントの最近傍を検索する必要があります。ただし、ポイントは常に移動しているため、kd ツリーのような静的データ構造を使用することはできません...

これを達成できる優れた (簡単な) データ構造/ライブラリは何ですか? 私はC++で作業しています...

外国為替市場向けの自動取引ソフトウェアを設計しています。MYSQL データベースには、5 分間隔で何年にもわたる市場データがあります。このデータには、価格と時間に加えて 5 つの異なる指標があります。

Timeが主キーで、M1さまざまM5な指標 (標準偏差や移動平均の傾きなど) があります。

M1、、、、および M5の入力が与えられた場合M2、最も近い 5,000 個の近傍を効率的に見つけるにはどうすればよいでしょうか? 各メトリックは浮動小数点であり、分布/範囲が異なることに注意してください。M3M4

私は外国為替市場向けの自動取引ソフトウェアを設計しています。MYSQLデータベースには、5分間隔で何年もの市場データがあります。価格と時間に加えて、このデータには4つの異なる指標があります。

Timeは主キーであり、M1スルーM4はさまざまなメトリック（標準偏差や移動平均の傾きなど）です。

これが実際の例です（抜粋:)

M1、、、の入力が与えられた場合、M2（迅速かつ正確に）5,000個の最も近い一致を見つけたいM3と思います。M4

サンプル入力：

これらの各メトリックは「ディメンション」と見なすことができnearest neighbor search、この多次元空間で最も近いデータポイントを見つけるために実行できると考えました。

これを行う最も簡単な方法は、すべてのデータポイントを反復処理し、入力ポイントまでの多次元距離を測定することです。しかし、スピードが重要です！

K-D Trees私はこの目的のために使用されると呼ばれるものについて読みました。誰かがMYSQLでこれを実装する方法を説明するいくつかの資料を説明または提供してくれますか？

テーブルを前処理することはできますが、入力はリアルタイムで受信されます。

現在、各ディメンションのデータの周りに個別に大まかなクラスターを作成しています。

私が興味を持っているのは、値ではなくランクによる距離であることを理解することが重要です。

編集：私はそれを行う方法を少し理解することに近づいています（私は思う）：各メトリックの各行を前処理percentileし、その範囲内の位置（パーセント単位）を表すaを割り当てる必要があります。

たとえば、次の任意の値に対してM1：

入力のパーセンタイルを計算し、それを実際の値の代わりに最近傍検索に使用すると、ディメンションとして使用できるようにさまざまなメトリックを効果的にスケーリングできます。

しかし、実際の検索方法についてはまだ迷っています。これはMySQLで効率的に達成することさえ可能ですか？

Fortuneの方法を使用して、2次元でボロノイ図を生成する方法を正常に実装しました。しかし今、私はそれをポイントの最近傍クエリに使用しようとしています（これはダイアグラムの生成に使用された元のポイントの1つではありません）。私はそれがO（lg n）時間でできると人々が言っ​​ているのを見続けています（そして私は彼らを信じています）が、それが実際にどのように行われたかについての説明を見つけることができません。

私は二分探索に精通していますが、その上限を保証するための適切な基準を理解することはできません。また、図にポイントを挿入して周囲のセルを更新することと関係があるかもしれないと考えましたが、それを行うための良い方法を考える（または見つける）ことはできません。

誰かが私を手がかりにしたり、より詳細な説明のある場所を指し示したりできますか？

次の擬似コードは、アルゴリズム設計マニュアルのオンラインプレビューバージョンの最初の章からのものです（このPDFの7ページ）。

この例は欠陥のあるアルゴリズムですが、それでも私はそれを本当に理解したいと思っています。

[...]別のアイデアは、サイクルの早期終了など、接続によって問題が発生しない最も近いエンドポイントのペアを繰り返し接続することです。各頂点は、独自の単一の頂点チェーンとして始まります。すべてをマージすると、すべてのポイントを含む単一のチェーンになります。最後の2つのエンドポイントを接続すると、サイクルが発生します。この最も近いペアのヒューリスティックの実行中の任意のステップで、マージに使用できる単一の頂点と頂点が互いに素なチェーンのセットがあります。擬似コードの場合：

とである必要があることに注意してsmください。tmsmtm

まず第一に、「異なる頂点チェーンから」が何を意味するのか理解できません。次に、i外側のループでカウンターとして使用されますが、iそれ自体が実際にどこでも使用されることはありません。私より賢い人がここで実際に何が起こっているのか説明してもらえますか？

ここで助けが必要です。私は実験的な Web フォーム デザインを行う数字が苦手な UI デザイナーであり、Web ページでクリックされたポイントに最も近い入力要素を知る必要があります。ポイントで最近傍を行う方法は知っていますが、入力要素はポイントではなく長方形であるため、行き詰まっています。

私はjQueryを使用しています。この小さなアルゴについて助けが必要です。実験が終わったら、私が何をしているかを皆さんにお見せします。

アップデート

どうすればうまくいくかを考えました。この図を見てください：

各長方形には、重要な 8 つのポイント (または 4 つのポイントと 4 つの線) があります。水平点 (赤い点) では x 値のみが重要であり、垂直点 (緑色の点) では y 値のみが重要です。コーナーでは x と y の両方が重要です。

Orange crosses are the points to be measured against – mouse clicks in my use case. The light purple lines are the distances between the orange cross and it's possible nearest point.

So… for any given orange cross, loop through each of the 8 points n every rectangle to find the nearest edge or corner closest of each rectangle to the orange cross. The rectangle with the lowest value is the nearest one.

I can conceptualize and visualize it but can't put it into code. Help!