論文の概要: LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2410.18926v1
• Date: Thu, 24 Oct 2024 17:13:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-25 12:49:10.813674
• Title: LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search
• Title（参考訳）: LoRANN: 近似近傍探索のための低ランク行列係数化
• Authors: Elias Jääsaari, Ville Hyvönen, Teemu Roos,
• Abstract要約: 本稿では,内積近似が多出力回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。 実験の結果,提案手法はクエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることがわかった。 また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。
• 参考スコア（独自算出の注目度）: 4.194768796374315
• License:
• Abstract: Approximate nearest neighbor (ANN) search is a key component in many modern machine learning pipelines; recent use cases include retrieval-augmented generation (RAG) and vector databases. Clustering-based ANN algorithms, that use score computation methods based on product quantization (PQ), are often used in industrial-scale applications due to their scalability and suitability for distributed and disk-based implementations. However, they have slower query times than the leading graph-based ANN algorithms. In this work, we propose a new supervised score computation method based on the observation that inner product approximation is a multivariate (multi-output) regression problem that can be solved efficiently by reduced-rank regression. Our experiments show that on modern high-dimensional data sets, the proposed reduced-rank regression (RRR) method is superior to PQ in both query latency and memory usage. We also introduce LoRANN, a clustering-based ANN library that leverages the proposed score computation method. LoRANN is competitive with the leading graph-based algorithms and outperforms the state-of-the-art GPU ANN methods on high-dimensional data sets.
• Abstract（参考訳）: 近似近傍探索(ANN)は、多くの現代の機械学習パイプラインにおいて重要な要素であり、最近のユースケースには、検索強化生成(RAG)とベクトルデータベースが含まれる。 製品量子化(PQ)に基づくスコア計算手法を使用するクラスタリングベースのANNアルゴリズムは、分散およびディスクベースの実装にスケーラビリティと適合性があるため、産業規模のアプリケーションでよく使用される。 しかし、主要なグラフベースのANNアルゴリズムよりもクエリ時間が遅い。 本研究では,内積近似が多変量(マルチアウトプット)回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。 提案手法は,最近の高次元データセットにおいて,クエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることを示す。 また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。 LoRANNは主要なグラフベースのアルゴリズムと競合し、高次元データセット上で最先端のGPU ANN法より優れている。

関連論文リスト

• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square Two-tower model, HNSW, Sign Cauchy Projections [17.542394573133777]
  グラフベースのANNアルゴリズムを用いてスパースデータの効率的な探索を探索する。 広告ターゲティングでは、標準のコサイン2-tower'モデルで埋め込みを訓練する。 また,Chi-square two-tower' モデルも開発している。
  論文  参考訳（メタデータ） (2023-06-13T08:05:30Z)
• ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms [5.478671305092084]
  本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。 我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
  論文  参考訳（メタデータ） (2023-05-07T19:28:23Z)
• AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilization [159.75564904944707]
  垂直連合学習(VFL)のための非同期準ニュートン(AsySQN)フレームワークを提案する。 提案アルゴリズムは、逆ヘッセン行列を明示的に計算することなく、近似して降下ステップをスケールする。 本稿では,非同期計算を採用することにより,計算資源の有効利用が期待できることを示す。
  論文  参考訳（メタデータ） (2021-09-26T07:56:10Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Robust Regression Revisited: Acceleration and Improved Estimation Rates [25.54653340884806]
  強い汚染モデルの下で, 統計的回帰問題に対する高速アルゴリズムについて検討する。 目的は、逆向きに破損したサンプルを与えられた一般化線形モデル(GLM)を概ね最適化することである。 実行時や推定保証が改善された頑健な回帰問題に対して,ほぼ直線的な時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T17:21:56Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。 我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
  論文  参考訳（メタデータ） (2021-05-18T05:23:53Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)
• A Robust Matching Pursuit Algorithm Using Information Theoretic Learning [37.968665739578185]
  情報理論学習(ITL)に基づく新しいOMPアルゴリズムの開発 シミュレーションおよび実世界の両方のデータに対する実験結果は、データ復元、画像再構成、分類において提案したOMPアルゴリズムの優位性を一貫して示している。
  論文  参考訳（メタデータ） (2020-05-10T01:36:00Z)
• Statistical Outlier Identification in Multi-robot Visual SLAM using Expectation Maximization [18.259478519717426]
  本稿では、同時局所化およびマッピング(SLAM)におけるマップ間ループ閉包外乱検出のための、新しい分散手法を提案する。 提案アルゴリズムは優れた初期化に頼らず、一度に2つ以上のマップを処理できる。
  論文  参考訳（メタデータ） (2020-02-07T06:34:44Z)

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

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