問題タブ [kdtree]

KD ツリーは最近傍検索に最適であると常に宣伝されています。ただし、データ セットがすべて離散値であり、実際の距離メトリックがない場合でも、それらは効率的でしょうか?

たとえば、属性が[black, blue, red], [bread, milk, cheese], [right, left, straight, curved]連続性がなく、距離を測定する唯一の方法がハミング距離のようなものである場合 (テスト例と同等の数を確認します)。これらのシナリオでも KD ツリーは有効に機能しますか? どうして？

KDツリーのウィキペディアページを見ています。例として、リストされているkdツリーを構築するためのアルゴリズムをPythonで実装しました。

ただし、KDツリーを使用してKNN検索を実行するためのアルゴリズムは言語を切り替え、完全には明確ではありません。英語の説明は意味をなし始めますが、その一部（他のリーフノードをチェックするために「再帰をほどく」領域など）は、私には実際には意味がありません。

これはどのように機能し、PythonでKDツリーを使用してKNN検索を実行するにはどうすればよいですか？これは"send me the code!"タイプの質問を意味するものではなく、私はそれを期待していません。簡単な説明をお願いします:)

次の形式のデータセットがあります。

日時 | 緯度 | 経度 | 身長 | 温度

これらのデータは、さまざまな空間と時間での大気温度測定値に基づいてユーザーが入力できます。空間は緯度、経度、高さで表されます。このデータ セットから、任意の空間と時間での温度を次のように取得する必要があります。補間.そのようなシナリオでどのようなデータ構造を使用する必要があるかわかりません.Kd-treeについて読みましたが、それはオプションですか?

私は現在、物理エンジン（趣味のプロジェクト）用のKDTreeを書いています。

KDTreeにはポイントが含まれていません。代わりに、環境内のさまざまなオブジェクトをバインドするAxisAlignedバウンディングボックスが含まれています。

私の問題は、KDTreeノードがいっぱいになったときに分割する方法を決定することです。私は2つの方法を試しています：

方法1：ノードを常に最大軸上で正確に半分に分割します。

• これには、かなり等間隔に配置されたツリーという利点があります。
• 大きな欠点：オブジェクトがノードの小さな領域に集中している場合、冗長なサブディビジョンが作成されます。これは、すべてのボリュームが正確に半分に分割されているためです。

方法2：オブジェクトを含むノードの領域を見つけます。最大軸上でその領域を半分に分割する平面上でノードを分割します。例-すべてのオブジェクトがノードの下部に集中している場合、オブジェクトは縦方向に分割され、それによって下部が2つに分割されます。

• これにより、上記の方法の問題が解決します
• 同じ平面上に存在するもの（たとえば地形）にインデックスを付けると、長くて狭いノードが作成されます。同じ平面上にない他のオブジェクトを後で追加する場合、これらの細長いノードは非常に貧弱なインデックスを提供します。

したがって、ここで探しているのは、KDツリーノードを分割するためのより良い方法です。これが物理エンジンになることを考えると、決定はリアルタイムで行われるのに十分単純である必要があります。

この質問への回答は非常に簡単で、このテーマに関するドキュメントはおそらくたくさんあると思いますが、検索で何も見つからなかったので、間違ったものを検索していると思います。

それぞれが1または0の値を持つ同じサイズの立方体の世界があると想像してみましょう。

同様の値の立方体を可能な限り最大の直方体にマージするための最良の方法は何ですか。ランダムに1つを取得し、隣接するノードをチェックして、それらがすべて同じあいまいで繰り返されている場合はそれらを組み合わせると考えましたが、明らかに結果は特に最適化されていません。また、キューブの可能なすべての組み合わせをチェックして結果を比較することも検討しましたが、それは非常にコストがかかります。

誰もがレンダリングできるどんな助けも非常に役に立ちます。

ああ、明確にするために、私はパスファインディングを最適化するのに役立つ直交衝突データからKDツリーを構築する方法を探しています。

マップ ポイントをグループにクラスター化する 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)

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

ありがとう。

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

関数は次のとおりです。

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

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

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

3空間のオブジェクトのセットでk最近傍問題を解こうとしています。これらのオブジェクトは、ドキュメント ベースのストレージに伴うすべての喜びと悲しみを備えた MongoDB コレクションに存在します。1 つのオブジェクトが与えられた場合、できるだけ少ないクエリで k 個の最近傍を見つけたいと考えています。コレクションのサイズは約 10^5 と予想され、k は 10 から 50 の間です。ツリー全体をメモリに保存する必要はありません。

KD ツリーを MongoDB コレクションに格納するにはどうすればよいですか?

SQL で実装されたKD-Tree、または同様の空間インデックスを知っている人はいますか? Python と Django の ORM を使用して独自のコードを作成することを検討していましたが、車輪の再発明は避けたいと考えています。

何百万もの行を含むテーブルがあり、各行には画像の特徴データを表す 128 列が含まれています。画像特徴の任意の 128 要素の長いリストが与えられた場合、KD ツリーを使用して、データベース内で最も類似した N 個の画像を見つけたいと考えています。多くの KD-Tree 実装を見つけましたが、それらはすべてローカル メモリにロードするだけで、スケーリングやデータベースとの通信は行わないようです。

文字列の類似性の問題にk最近傍法を利用しようとしています。つまり、文字列と知識ベースが与えられた場合、与えられた文字列に類似したk個の文字列を出力したいと思います。kdツリーを利用して文字列のこのk最近傍ルックアップを効率的に行う方法を説明するチュートリアルはありますか？文字列の長さは20文字を超えてはなりません。