論文の概要: Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search
- arxiv url: http://arxiv.org/abs/2410.20381v1
- Date: Sun, 27 Oct 2024 09:12:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-10 12:02:07.071280
- Title: Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search
- Title（参考訳）: グラフに基づく近似近傍探索による高密度疎ハイブリッドベクトルの効率的・効果的検索
- Authors: Haoyu Zhang, Jun Liu, Zhenhua Zhu, Shulin Zeng, Maojia Sheng, Tao Yang, Guohao Dai, Yu Wang,
- Abstract要約: グラフに基づく高密度疎ハイブリッドベクトルのためのANNSアルゴリズムを提案する。
提案アルゴリズムは,既存のハイブリッドベクトル探索アルゴリズムと同等の精度で8.9x$sim$11.7xスループットを実現する。
- 参考スコア（独自算出の注目度）: 14.821492155733555
- License:
- Abstract: ANNS for embedded vector representations of texts is commonly used in information retrieval, with two important information representations being sparse and dense vectors. While it has been shown that combining these representations improves accuracy, the current method of conducting sparse and dense vector searches separately suffers from low scalability and high system complexity. Alternatively, building a unified index faces challenges with accuracy and efficiency. To address these issues, we propose a graph-based ANNS algorithm for dense-sparse hybrid vectors. Firstly, we propose a distribution alignment method to improve accuracy, which pre-samples dense and sparse vectors to analyze their distance distribution statistic, resulting in a 1%$\sim$9% increase in accuracy. Secondly, to improve efficiency, we design an adaptive two-stage computation strategy that initially computes dense distances only and later computes hybrid distances. Further, we prune the sparse vectors to speed up the calculation. Compared to naive implementation, we achieve $\sim2.1\times$ acceleration. Thorough experiments show that our algorithm achieves 8.9x$\sim$11.7x throughput at equal accuracy compared to existing hybrid vector search algorithms.
- Abstract（参考訳）: テキストの埋め込みベクトル表現のためのANNSは、情報検索において一般的に使われており、2つの重要な情報表現は疎密なベクトルである。
これらの表現を組み合わせることで精度が向上することが示されているが、現在の疎度ベクトル探索法と密度ベクトル探索法は、スケーラビリティの低下とシステム複雑性の増大に悩まされている。
あるいは、統合インデックスの構築は、正確性と効率性の面で課題に直面します。
これらの問題に対処するため,高密度なハイブリッドベクトルに対するグラフベースANNSアルゴリズムを提案する。
まず, 精度向上のための分布アライメント手法を提案し, その距離分布統計を解析するために, 密度ベクトルとスパースベクトルを事前サンプリングし, 精度を1%$\sim$9%向上させる。
第二に、効率を向上させるために、まず高密度距離のみを計算し、後にハイブリッド距離を演算する適応的な2段階計算戦略を設計する。
さらに、スパースベクトルを練習して計算を高速化する。
単純な実装と比較すると、$\sim2.1\times$Acceleratorが得られます。
より詳細な実験により,本アルゴリズムは既存のハイブリッドベクトル探索アルゴリズムと同等の精度で8.9x$\sim$11.7xスループットを達成した。
関連論文リスト
- Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - RSC: Accelerating Graph Neural Networks Training via Randomized Sparse
Computations [56.59168541623729]
トレーニンググラフニューラルネットワーク(GNN)は、疎グラフベースの操作がハードウェアによって加速することが難しいため、時間を要する。
我々は,サンプリングに基づく近似による時間的複雑性を低減するために,計算精度のトレードオフを検討する。
本稿では,GNNを近似演算でトレーニングする可能性を初めて示すランダム化スパース計算を提案する。
論文 参考訳（メタデータ） (2022-10-19T17:25:33Z) - Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。
実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。
本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-13T02:44:05Z) - Fast Projection onto the Capped Simplex withApplications to Sparse
Regression in Bioinformatics [6.6371396313325075]
ニュートン法に基づく単純なアルゴリズムは、射影問題を高精度に解くことができる。
提案アルゴリズムは,大規模データセット上で高い精度で予測問題の解を導出できることを実証する。
論文 参考訳（メタデータ） (2021-10-16T05:03:24Z) - Kernel Density Estimation by Stagewise Algorithm with a Simple
Dictionary [0.0]
本稿では,U-divergenceの簡単な辞書を用いて,ステージワイズアルゴリズムによるカーネル密度推定について検討する。
i.d.サンプルをランダムに2つの非結合集合に分割し,その1つは辞書内のカーネルを構築するためのもので,もう1つは推定器を評価するためのものである。
論文 参考訳（メタデータ） (2021-07-27T17:05:06Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。