論文の概要: nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds

• arxiv url: http://arxiv.org/abs/2610.15215v1
• Date: Sat, 10 Oct 2026 23:10:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 02:03:42.482027
• Title: nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds
• Title（参考訳）: nanoflann: コンパイル時の製品マニフォールドに関する非常に近い検索のためのヘッダ専用KD-Treeライブラリ
• Abstract要約: Nearest-Nighbor (NN) 検索は無数のロボットアルゴリズムを基盤としているが、多くの状態空間はユークリッドではない。 NN 検索のためのヘッダのみの依存性のない C++ KD-tree ライブラリを提示する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Nearest-neighbor (NN) search underlies countless robotics algorithms, but many state spaces are not Euclidean: orientations live on $SO(2)$ or $SO(3)$ and poses on $SE(2)$ or $SE(3)$, and a Euclidean KD-tree on their raw coordinates returns wrong neighbors. We present a header-only, dependency-free C++ KD-tree library for exact NN search on user-defined product manifolds declared at compile time: the space is composed from base manifolds ($\mathbb{R}^n$, $SO(2)$, $SO(3)$, $S^n$; products $SE(2)$, $SE(3)$, tori) with a single type alias, and the library synthesizes a metric whose pruning is provably admissible, wrap-aware for circular coordinates and double-cover-aware for unit quaternions. Experiments confirm exactness (recall $1.0$ vs an exhaustive scan under the same product metric), where the Euclidean-on-raw shortcut collapses to recall $\approx 0.5^{m}$ for $m$ rotation blocks, with up to three orders of magnitude speedup over brute force. We further contribute an incremental, self-balancing single-tree index for points under heavy churn (e.g. sliding-window LiDAR maps) or $SE(3)$ trajectories: bounded memory and faster updates than prior work, with an optional asynchronous tail-latency-bounding mode. The implementation is open source: https://github.com/jlblancoc/nanoflann
• Abstract（参考訳）: Nearest-Nighbor (NN) 検索は無数のロボティクスアルゴリズムを基盤としているが、多くの状態空間はユークリッドではない:$SO(2)$または$SO(3)$に居住し、$SE(2)$または$SE(3)$に作用する。 この空間は、単一の型エイリアスを持つ基本多様体($\mathbb{R}^n$, $SO(2)$, $SO(3)$, $S^n$; product $SE(2)$, $SE(3)$, tori)からなり、このライブラリはプルーニングが許容できる距離を合成する。 実験は正確性を確認する(同じ積の計量で1.0$対排他的スキャン)が、ユークリッド・オン・ローのショートカットは崩壊して$\approx 0.5^{m}$を$m$回転ブロックで呼び戻す。 さらに、重いチャーン(例えば、スライドウインドウのLiDARマップ)または$SE(3)$トラジェクトリの下のポイントに対して、インクリメンタルで自己バランスのシングルツリーインデックスをコントリビュートします。 実装はオープンソースである。 https://github.com/jlblancoc/nanoflann

関連論文リスト

• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression [0.0]
  Algebraic Replay Engineは、ポインターレスDSSとインデックスなしストリーミングとともに、一定の大きさのフィールド上の一定度マップを持つ。 S(b)=O(b+t/b)$は、残余乗法的ポリログ因子を持たない$O(sqrtt)$空間を与える。
  論文  参考訳（メタデータ） (2025-08-20T16:27:53Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
  論文  参考訳（メタデータ） (2024-05-07T15:57:39Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Empirical complexity of comparator-based nearest neighbor descent [0.0]
  K$-nearest 隣り合うアルゴリズムの Java 並列ストリームの実装を示す。 Kullback-Leiblerの発散比較器による実験は、$K$-nearest近くの更新ラウンドの数が直径の2倍を超えないという予測を支持している。
  論文  参考訳（メタデータ） (2022-01-30T21:37:53Z)
• Coresets for Decision Trees of Signals [19.537354146654845]
  仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。 これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
  論文  参考訳（メタデータ） (2021-10-07T05:49:55Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。