論文の概要: Fast top-K Cosine Similarity Search through XOR-Friendly Binary
Quantization on GPUs
- arxiv url: http://arxiv.org/abs/2008.02002v1
- Date: Wed, 5 Aug 2020 08:50:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 18:48:54.574779
- Title: Fast top-K Cosine Similarity Search through XOR-Friendly Binary
Quantization on GPUs
- Title(参考訳): GPU上のXORフレンドリなバイナリ量子化による高速トップKコサイン類似検索
- Authors: Xiaozheng Jian, Jianqiu Lu, Zexi Yuan, Ao Li
- Abstract要約: このアルゴリズムは、浮動小数点数をエンコードするために、新しいXORフレンドリなバイナリ量子化法を用いる。
実験により,我々の量子化法は前処理時間を短縮し,探索手法の探索速度を近辺のアルゴリズムよりもはるかに速くすることがわかった。
- 参考スコア(独自算出の注目度): 1.5828697880068703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We explore the use of GPU for accelerating large scale nearest neighbor
search and we propose a fast vector-quantization-based exhaustive nearest
neighbor search algorithm that can achieve high accuracy without any indexing
construction specifically designed for cosine similarity. This algorithm uses a
novel XOR-friendly binary quantization method to encode floating-point numbers
such that high-complexity multiplications can be optimized as low-complexity
bitwise operations. Experiments show that, our quantization method takes short
preprocessing time, and helps make the search speed of our exhaustive search
method much more faster than that of popular approximate nearest neighbor
algorithms when high accuracy is needed.
- Abstract(参考訳): 本稿では,gpuを用いた大規模近接探索の高速化について検討し,コサイン類似性を考慮したインデクシング構成を必要とせず,高精度なベクトル量子化に基づく排他的近傍探索アルゴリズムを提案する。
このアルゴリズムは、新しいxorフレンドリーなバイナリ量子化法を用いて浮動小数点数を符号化し、高複素乗算を低複素ビット演算として最適化する。
実験の結果, 量子化法では, 事前処理に要する時間が短く, 高い精度が必要となる場合, 探索速度が近距離探索法よりも高速であることが判明した。
関連論文リスト
- Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
本稿ではHastingsが最初に提案したショートパスフレームワークに基づいてアルゴリズムの一般化を分析する。
一般的に満たされているいくつかの技術的条件の下では、適切な一般化は超4次スピードアップを達成することができる。
本論文は,短経路アルゴリズムのパラメータ選択を導く数値解析で締めくくった。
論文 参考訳(メタデータ) (2024-10-30T17:52:56Z) - Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search [14.821492155733555]
グラフに基づく高密度疎ハイブリッドベクトルのためのANNSアルゴリズムを提案する。
提案アルゴリズムは,既存のハイブリッドベクトル探索アルゴリズムと同等の精度で8.9x$sim$11.7xスループットを実現する。
論文 参考訳(メタデータ) (2024-10-27T09:12:51Z) - 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) - 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) - Locality-aware Qubit Routing for the Grid Architecture [1.4459640831465588]
本稿では,グラフ理論に基づく局所性を考慮した量子ビットルーティングアルゴリズムを提案する。
我々のアルゴリズムはグリッドとある種の"グリッドのような"アーキテクチャのために設計されている。
論文 参考訳(メタデータ) (2022-03-21T20:46:39Z) - Nearest neighbor search with compact codes: A decoder perspective [77.60612610421101]
バイナリハッシュや製品量化器などの一般的な手法を自動エンコーダとして再解釈する。
後方互換性のあるデコーダを設計し、同じ符号からベクトルの再構成を改善する。
論文 参考訳(メタデータ) (2021-12-17T15:22:28Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Fast Search on Binary Codes by Weighted Hamming Distance [38.50174794945964]
ハンミング距離を重み付けして最寄りの2進符号を$K$で探索する高速探索アルゴリズムが提案されている。
提案した探索アルゴリズムに基づく高速探索フレームワークは,長いバイナリ符号の問題を解くために設計されている。
論文 参考訳(メタデータ) (2020-09-18T02:24:44Z) - Faster Person Re-Identification [68.22203008760269]
本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。
より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。
2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
論文 参考訳(メタデータ) (2020-08-16T03:02:49Z) - Hybrid divide-and-conquer approach for tree search algorithms [0.0]
本稿では,木探索アルゴリズムの文脈におけるハイブリッド分割・コンカレント手法について検討する。
DPLLのアルゴリズムの高速化条件について述べる。
本稿では,大規模問題に対する高速化におけるハイブリッド手法の限界について概説する。
論文 参考訳(メタデータ) (2020-07-14T13:57:12Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。