論文の概要: Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2409.09913v1
• Date: Mon, 16 Sep 2024 01:06:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 15:26:44.017021
• Title: Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search
• Title（参考訳）: 近似近傍探索のためのユークリッド空間における高次元ベクトルの実用的および漸近的最適量子化
• Authors: Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, Raymond Chi-Wing Wong,
• Abstract要約: 本稿では、RaBitQの理論的保証を継承し、空間とエラー境界のトレードオフの観点から最適性を実現する、RaBitQと呼ばれる新しい量子化手法を提案する。 提案手法は,同じメモリ量を使用する場合の精度と効率の両方において,最先端のベースラインを一貫して上回る。
• 参考スコア（独自算出の注目度）: 30.003470912691096
• License:
• Abstract: Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Recently, a method called RaBitQ achieves the state-of-the-art performance among these methods. It produces better empirical performance in both accuracy and efficiency when using the same compression rate and provides rigorous theoretical guarantees. However, the method is only designed for compressing vectors at high compression rates (32x) and lacks support for achieving higher accuracy by using more space. In this paper, we introduce a new quantization method to address this limitation by extending RaBitQ. The new method inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the method, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.
• Abstract（参考訳）: 高次元ユークリッド空間における近似近傍クエリ(ANN)は、データベースシステムにおいて重要な演算子である。 このクエリのために、量子化はベクトルを圧縮し、メモリ消費を減らすために開発された一般的な手法のファミリーである。 近年,RaBitQと呼ばれる手法が,これらの手法の最先端性能を実現している。 同じ圧縮速度を使用する場合、精度と効率の両方で実験性能が向上し、厳密な理論的保証を提供する。 しかし、この手法はベクトルを高い圧縮速度 (32x) で圧縮するためにのみ設計されており、より多くの空間を用いることで高い精度を達成するためのサポートを欠いている。 本稿では,RaBitQを拡張した新しい量子化手法を提案する。 提案手法は,RaBitQの理論的保証を継承し,空間境界と誤差境界とのトレードオフの観点から漸近的最適性を実現する。 さらに,提案手法の効率的な実装を行い,ANNクエリに適用することで,空間と時間の両方を削減できることを示す。 実世界のデータセットに対する大規模な実験により、同じ量のメモリを使用する場合の精度と効率の両方において、我々の手法が常に最先端のベースラインを上回ることが確認された。

関連論文リスト

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。 WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
  論文  参考訳（メタデータ） (2024-10-28T04:47:39Z)
• LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search [4.194768796374315]
  本稿では,内積近似が多出力回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。 実験の結果,提案手法はクエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることがわかった。 また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。
  論文  参考訳（メタデータ） (2024-10-24T17:13:39Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• l1-norm regularized l1-norm best-fit lines [3.0963566281269594]
  簡単な比率とソート手法を用いた新しいフィッティング法を提案する。 提案アルゴリズムは、O$(n2 m log n)$の最悪の時間複雑性を示し、ある場合にはスパース部分空間に対する大域的最適性を達成する。
  論文  参考訳（メタデータ） (2024-02-26T16:30:58Z)
• A Computationally Efficient Sparsified Online Newton Method [48.78646010774149]
  Sparsified Online Newton (SONew) はメモリ効率の良い2次アルゴリズムである。 最大で30%の高速化,3.4%の妥当性向上,80%のトレーニング損失の相対的改善を実現しています。
  論文  参考訳（メタデータ） (2023-11-16T18:44:22Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Similarity search in the blink of an eye with compressed indices [3.39271933237479]
  グラフベースのインデックスは現在、数十億の類似性検索において、最高のパフォーマンス技術である。 より高速でより小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
  論文  参考訳（メタデータ） (2023-04-07T23:10:39Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
  微分可能なアーキテクチャサーチ (DARTS) は、NASの高効率性のため、一般的なワンショットパラダイムである。 この作業はゼロオーダーの最適化に変わり、上記の近似を強制せずに探索するための新しいNASスキームであるZARTSを提案する。 特に、12ベンチマークの結果は、DARTSの性能が低下するZARTSの顕著な堅牢性を検証する。
  論文  参考訳（メタデータ） (2021-10-10T09:35:15Z)
• One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
  1ビット圧縮センシングの問題は、いくつかのバイナリ測定からスパース信号を推定することである。 広範に使われている非制約の幅の概念から遠ざかる、斬新で簡潔な分析法を提案する。
  論文  参考訳（メタデータ） (2020-07-07T17:28:03Z)

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

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