論文の概要: Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

• arxiv url: http://arxiv.org/abs/2607.01283v1
• Date: Wed, 01 Jul 2026 08:42:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-03 19:45:08.523454
• Title: Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions
• Title（参考訳）: 高次元における格子近似近傍探索のスケーリング法則
• Abstract要約: 我々は,データセットサイズが$N$,次元が$d$に対して,マルチプローブグリッドアルゴリズムの体系的特性を示す。 その結果、マルチプローブグリッドのようなグリッドベースの手法は、再構築重度や高次元設定において競合する可能性が示唆された。
• 参考スコア（独自算出の注目度）: 4.018187102803958
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grid-based approaches to approximate nearest neighbor (ANN) search have been absent from modern scaling analyses. We present a systematic characterization of a multiprobe grid algorithm with respect to dataset size $N$ and dimensionality $d$. Our experiments reveal a previously unreported $d$-scaling crossover on the GloVe embedding family, in which multiprobe grid search maintains an approximately constant dimensional scaling exponent while other graph-, tree-, and partitioning-based methods exhibit degrading throughput. The advantage comes with near-linear query scaling in $N$, but also with lower indexing cost than competing ANN methods. Our results suggest that grid-based methods such as multiprobe grid may be competitive in rebuild-heavy or high-dimensional settings where indexing cost and dimensional robustness dictate performance. More broadly, recent work has formalized self-attention as an ANN operation. Thus, the $N$- and $d$-scaling properties of ANN algorithms may guide cost analysis of efficient transformer architectures. Code is available at: https://github.com/weiz345/MultiProbeANN.
• Abstract（参考訳）: 近距離近接探索(ANN)に対するグリッドベースのアプローチは、現代のスケーリング分析には欠落している。 我々は,データセットサイズが$N$,次元が$d$に対して,マルチプローブグリッドアルゴリズムの体系的特性を示す。 実験の結果,GloVe 埋め込みファミリ上には以前報告されていない$d$-scaling クロスオーバーが示され,マルチプローブグリッド探索は,グラフ,ツリー,パーティショニングに基づく他の手法が劣化スループットを示すのに対して,ほぼ一定次元のスケーリング指数を維持できることがわかった。 利点は、N$のニアリニアクエリスケーリングに加えて、競合するANNメソッドよりもインデックスコストが低いことだ。 この結果から,マルチプローブグリッドなどのグリッドベース手法は,インデクシングコストと次元ロバスト性によって性能が決定されるような,再構築重度や高次元設定において競合する可能性が示唆された。 より広範に、最近の研究はANNの運営として自己注意を定式化した。 したがって、ANNアルゴリズムの$N$-および$d$-scaling特性は、効率的なトランスフォーマーアーキテクチャのコスト分析を導くことができる。 コードは、https://github.com/weiz345/MultiProbeANN.comで入手できる。

関連論文リスト

• δ-EMG: A Monotonic Graph Index for Approximate Nearest Neighbor Search [33.62724124122037]
  本稿では,クエリ時における近似精度を制御する誤り境界付きANN探索アルゴリズムを提案する。 0.99のリコール条件下では、SIFT1Mデータセット上で19,000QPSを達成し、他の手法よりも40%以上性能が向上する。
  論文  参考訳（メタデータ） (2025-11-21T03:20:54Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  我々は、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を減らすことができることを示した。 任意の異方性測度を持つデータセットを$q$-metric空間に埋め込む新しい射影法を提案する。
  論文  参考訳（メタデータ） (2025-06-06T22:09:44Z)
• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations [20.944914202453962]
  グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
  論文  参考訳（メタデータ） (2023-10-29T19:25:48Z)
• ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms [5.478671305092084]
  本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。 我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
  論文  参考訳（メタデータ） (2023-05-07T19:28:23Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• 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)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
  論文  参考訳（メタデータ） (2020-03-24T19:39:34Z)

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

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