論文の概要: Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2602.08097v1
• Date: Sun, 08 Feb 2026 19:34:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.980148
• Title: Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search
• Title（参考訳）: Prune, Don't Rebuild: 近くの検索に$α$-reachableグラフを効率よく調整する
• Authors: Tian Zhang, Ashwin Padaki, Jiaming Liang, Zack Ives, Erik Waingarten,
• Abstract要約: 完全なインデックスを再構築することなく$$$パラメータを調整するRP-Tuningを提案する。 RP-Tuningは、4つの公開データセットのDiskANNチューニングを、無視できないオーバーヘッドで最大43タイムで高速化することを示す。
• 参考スコア（独自算出の注目度）: 7.168741876130465
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vector similarity search is an essential primitive in modern AI and ML applications. Most vector databases adopt graph-based approximate nearest neighbor (ANN) search algorithms, such as DiskANN (Subramanya et al., 2019), which have demonstrated state-of-the-art empirical performance. DiskANN's graph construction is governed by a reachability parameter $α$, which gives a trade-off between construction time, query time, and accuracy. However, adaptively tuning this trade-off typically requires rebuilding the index for different $α$ values, which is prohibitive at scale. In this work, we propose RP-Tuning, an efficient post-hoc routine, based on DiskANN's pruning step, to adjust the $α$ parameter without reconstructing the full index. Within the $α$-reachability framework of prior theoretical works (Indyk and Xu, 2023; Gollapudi et al., 2025), we prove that pruning an initially $α$-reachable graph with RP-Tuning preserves worst-case reachability guarantees in general metrics and improved guarantees in Euclidean metrics. Empirically, we show that RP-Tuning accelerates DiskANN tuning on four public datasets by up to $43\times$ with negligible overhead.
• Abstract（参考訳）: ベクトル類似性探索は、現代のAIおよびMLアプリケーションにおいて必須のプリミティブである。 ほとんどのベクトルデータベースは、最先端の実証的な性能を示すDiskANN(Subramanya et al , 2019)のようなグラフベースの近接探索アルゴリズム(ANN)を採用している。 DiskANNのグラフ構築は、建設時間、クエリ時間、正確性の間のトレードオフを与える、リーチビリティパラメータ$α$で管理されている。 しかし、このトレードオフを適応的に調整するには、通常、様々な$α$値のインデックスを再構築する必要がある。 本研究では,DiskANNのプルーニングステップに基づく効率的なポストホックルーチンRP-Tuningを提案する。 従来の理論研究の$α$-reachabilityフレームワーク(Indyk and Xu, 2023; Gollapudi et al , 2025)の中で、当初$α$-reachable graph を RP-Tuning でプルーニングすることは、一般的な測度における最悪の到達性保証を保ち、ユークリッド測度における保証を改善していることを証明している。 実証的に、RP-Tuningは4つの公開データセットのDiskANNチューニングを、無視可能なオーバーヘッドで最大43\times$で高速化する。

関連論文リスト

• GoPrune: Accelerated Structured Pruning with $\ell_{2,p}$-Norm Optimization [9.51204051181328]
  畳み込みニューラルネットワーク(CNN)は、その深さが大きくなるにつれて、ストレージと計算コストが急速に増大する。 本稿では,これらの制約を克服するために,GoPruneと呼ばれる高速な構造化プルーニング手法を提案する。 ResNet と VGG モデルを用いた CIFAR データセットの実験により,提案手法のネットワークプルーニングにおける優れた性能を示す。
  論文  参考訳（メタデータ） (2025-11-27T05:24:31Z)
• δ-EMG: A Monotonic Graph Index for Approximate Nearest Neighbor Search [33.62724124122037]
  本稿では,クエリ時における近似精度を制御する誤り境界付きANN探索アルゴリズムを提案する。 0.99のリコール条件下では、SIFT1Mデータセット上で19,000QPSを達成し、他の手法よりも40%以上性能が向上する。
  論文  参考訳（メタデータ） (2025-11-21T03:20:54Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations [20.944914202453962]
  グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
  論文  参考訳（メタデータ） (2023-10-29T19:25:48Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach [9.13755431537592]
  本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。 提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
  論文  参考訳（メタデータ） (2023-01-01T10:57:36Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Private Frequency Estimation via Projective Geometry [47.112770141205864]
  そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometryResponse (PGR)を提案する。 私たちの$varepsilon$-LDPアルゴリズムは、プライベートコイン設定で$lceillogkrceilビット、パブリックコイン設定で$varepsilonlog e + O(1)$の通信コストを持っています。 実際に使用される多くのパラメータ設定では、これは最近のPIによって達成されるO(n+k2)$Optimalコストよりも大幅に改善されている。
  論文  参考訳（メタデータ） (2022-03-01T02:49:55Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)

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

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