論文の概要: KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees

• arxiv url: http://arxiv.org/abs/2610.16940v1
• Date: Mon, 12 Oct 2026 15:17:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.39426
• Title: KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees
• Title（参考訳）: KNNの実装詳細は、パフォーマンスを劇的に変えることができる:カバーツリーの例
• Abstract要約: RustKNNは、3つのクエリモードを持つCover Treeの3つの構築版の実装である。 最適なクエリ戦略は、$k$とデータセットに依存する。 間違ったクエリモードを選択するには、実行時に最大$7.5times$ factorがかかる。
• 参考スコア（独自算出の注目度）: 40.37604203960131
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nearest neighbor search algorithms are widely used and have a long history, but we find that key implementation details are seldom reviewed in articles about them. These details can materially impact performance, and thus change the conclusions one makes about a given algorithm's superiority. In this article, we highlight these impacts by reviewing the Cover Tree as an example, producing RustKNN, a unified Rust implementation of three construction variants of the Cover Tree with three query modes. Our analysis reveals: (1) the optimal query strategy depends on $k$ and on the dataset (single-tree search is fastest at $k{=}1$ on three of our four largest datasets, while dual-tree search is fastest at $k{\ge}5$ on the three largest), and choosing the wrong query mode can cost up to a $7.5\times$ factor in runtime; (2) the cover tree base parameter, set to 2 in theory and 1.3 in practice, is not a safe default for dual-tree search: 1.3 is optimal on only one of seven datasets, and on covtype it is $1.6\times$ slower than the optimum; (3) among five micro-optimizations, only early-exit distance computation has a consistent effect, and that effect grows with dimension (none at $d{=}32$, $1.31\times$ at $d{=}54$, and $1.49\times$ at $d{=}784$); and (4) all-nearest-neighbor and held-out benchmarks yield different implementation rankings. All main timing tables report medians over 20 independent allocations with bootstrap 95% confidence intervals. RustKNN is open source at https://github.com/CrowdStrike/RustKNN.
• Abstract（参考訳）: 近隣の検索アルゴリズムは広く使われ、長い歴史があるが、重要な実装の詳細はそれらの記事にはほとんどレビューされない。 これらの詳細は性能に大きな影響を与える可能性があるため、与えられたアルゴリズムの優越性に関する結論を変更することができる。 本稿では、Cover Treeを例としてレビューし、3つのクエリモードを備えたCover Treeの3つの構成バリアントのRust実装であるRustKNNを作成することで、これらの影響を強調します。 1) 最適なクエリ戦略はデータセットの$k$とデータセットに依存する(4つの大きなデータセットのうち、シングルツリーの検索が$k{=}1$で最速であるのに対し、デュアルツリーの検索が$k{\ge}5$で最速である)。そして、間違ったクエリモードを選択すると、実行時に最大$7.5\times$ factorを選択できる。 (2) カバーツリーのベースパラメータは2に設定され、1.3は7つのデータセットのうちの1つで最適であり、コブタイプでは1.6\times$は最適値よりも遅い。 主要なタイミング表はすべて、ブートストラップ95%の信頼区間を持つ20以上の独立したアロケーションを中央値に報告している。 RustKNNはhttps://github.com/CrowdStrike/RustKNNでオープンソース公開されている。

関連論文リスト

• nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds [0.0]
  Nearest-Nighbor (NN) 検索は無数のロボットアルゴリズムを基盤としているが、多くの状態空間はユークリッドではない。 NN 検索のためのヘッダのみの依存性のない C++ KD-tree ライブラリを提示する。
  論文  参考訳（メタデータ） (2026-10-10T23:10:40Z)
• TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference [0.0]
  ここでは、グループ推論に部分評価を適用するTreeWalkerを提案する。 グループごとに各ツリーを1回歩き、様々な分割で行のビットマスクを分割し、空のサブツリーをスキップする。 トレース評価器に対しては、行独立ウォークの$(d_v+1)/(d+1)$分を infty$ に$G としてアプローチする。
  論文  参考訳（メタデータ） (2026-10-02T18:49:59Z)
• Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search [7.168741876130465]
  完全なインデックスを再構築することなく$$$パラメータを調整するRP-Tuningを提案する。 RP-Tuningは、4つの公開データセットのDiskANNチューニングを、無視できないオーバーヘッドで最大43タイムで高速化することを示す。
  論文  参考訳（メタデータ） (2026-02-08T19:34:38Z)
• Approximating splits for decision trees quickly in sparse data streams [6.184770559759073]
  スパースバイナリ機能とバイナリクラスを扱う場合、最適な分割の検索を高速化する方法に焦点をあてる。 我々の実験では、ほぼ最適で、ベースラインよりも高速で、理論近似の保証を上回ります。
  論文  参考訳（メタデータ） (2026-01-18T18:19:28Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• On the Power of Learning-Augmented Search Trees [7.325724756104182]
  本稿では,Treapsを用いた学習強化二分探索木(BST)について,慎重に設計した優先順位で検討する。 その結果、各項目の深さが予測重量$w_x$によって決定される単純な探索木となる。
  論文  参考訳（メタデータ） (2022-11-16T22:50:40Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃 提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。 私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
  論文  参考訳（メタデータ） (2020-10-22T10:59:49Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。 我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
  論文  参考訳（メタデータ） (2020-08-20T03:42:40Z)

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

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