論文の概要: Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations

• arxiv url: http://arxiv.org/abs/2310.19126v1
• Date: Sun, 29 Oct 2023 19:25:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-31 14:11:13.152559
• Title: Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
• Title（参考訳）: 一般近似近傍探索実装の最悪の性能:保証と制限
• Authors: Piotr Indyk, Haike Xu
• Abstract要約: グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
• 参考スコア（独自算出の注目度）: 20.944914202453962
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph-based approaches to nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. We study the worst-case performance of recent graph-based approximate nearest neighbor search algorithms, such as HNSW, NSG and DiskANN. For DiskANN, we show that its "slow preprocessing" version provably supports approximate nearest neighbor search query with constant approximation ratio and poly-logarithmic query time, on data sets with bounded "intrinsic" dimension. For the other data structure variants studied, including DiskANN with "fast preprocessing", HNSW and NSG, we present a family of instances on which the empirical query time required to achieve a "reasonable" accuracy is linear in instance size. For example, for DiskANN, we show that the query procedure can take at least $0.1 n$ steps on instances of size $n$ before it encounters any of the $5$ nearest neighbors of the query.
• Abstract（参考訳）: グラフベースの近接探索アプローチは、大規模データセットを実際に扱うための人気があり強力なツールであるが、理論上の保証は限られている。 本稿では,HNSW,NSG,DiskANNなどのグラフベース近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、「スロープリプロセッシング」バージョンは、有界な「内在的」次元のデータセット上で、近似比が一定であり、多対数的なクエリ時間を持つ近傍の探索クエリを確実にサポートする。 高速プリプロセッシングを備えたDiskANNやHNSW,NSGなどの他のデータ構造変種について,"理にかなった"精度を達成するのに必要な経験的クエリ時間が,インスタンスサイズで線形であることを示す。 例えば、 diskann の場合、クエリプロシージャは、クエリの最も近い5ドルの近傍のいずれかに遭遇する前に、サイズが$n$ のインスタンスに対して少なくとも$0.1 n$ のステップを取ることができる。

関連論文リスト

• 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)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• 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)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Systematically improving existing k-means initialization algorithms at nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
  PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。 与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
  論文  参考訳（メタデータ） (2022-02-08T15:56:30Z)
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search [8.25574589820305]
  近似近傍近傍近傍(DEANN)からの密度推定アルゴリズムを提案する。 我々は、非バイアス密度推定(KDE)を計算するために、ANNアルゴリズムをブラックボックスサブルーチンとして適用する。 我々の実装は、検討したすべての高次元データセットにおいて、技術実装の状況よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-06T17:11:28Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)
• Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms [0.0]
  与えられたクエリポイントのデータセットでk-nearestの隣人を見つける問題は、数年前から解決されてきた。 本稿では,K-Nearest Neighbor Search(K-Nearest Neighbor Search)の手法について,計算の視点から検討する。 本論文では,KNNSアプローチの対敵点に対する堅牢性を評価するために,汎用的な強化学習ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-02-10T16:10:58Z)
• Cross-Domain Generalization Through Memorization: A Study of Nearest Neighbors in Neural Duplicate Question Detection [72.01292864036087]
  重複質問検出(DQD)は,コミュニティの効率向上と自動質問応答システムの実現に重要である。 我々は、DQDのクロスドメイン一般化のために、ニューラル表現を活用し、近接する隣人を研究する。 StackExchange、Spring、Quoraの各データセットの異なるクロスドメインシナリオにおいて、このメソッドの堅牢なパフォーマンスを観察します。
  論文  参考訳（メタデータ） (2020-11-22T19:19:33Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)

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

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