論文の概要: Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2411.17229v2
• Date: Sun, 01 Dec 2024 13:20:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-03 13:35:43.241759
• Title: Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search
• Title（参考訳）: 高次元近似近傍探索のための効率的なデータ認識距離比較操作
• Authors: Liwei Deng, Penghao Chen, Ximu Zeng, Tianfu Wang, Yan Zhao, Kai Zheng,
• Abstract要約: 高次元近似$K$近接探索(AKNN)は情報検索を含む様々なアプリケーションの基本課題である。 AKNNの既存のアルゴリズムのほとんどは、候補生成と距離比較演算(DCO)という2つの主要コンポーネントに分解することができる。 低次元空間における正確な距離を近似するDADEと呼ばれるデータ認識距離推定手法を提案する。
• 参考スコア（独自算出の注目度）: 14.77572360618428
• License:
• Abstract: High-dimensional approximate $K$ nearest neighbor search (AKNN) is a fundamental task for various applications, including information retrieval. Most existing algorithms for AKNN can be decomposed into two main components, i.e., candidate generation and distance comparison operations (DCOs). While different methods have unique ways of generating candidates, they all share the same DCO process. In this study, we focus on accelerating the process of DCOs that dominates the time cost in most existing AKNN algorithms. To achieve this, we propose an Data-Aware Distance Estimation approach, called DADE, which approximates the exact distance in a lower-dimensional space. We theoretically prove that the distance estimation in DADE is unbiased in terms of data distribution. Furthermore, we propose an optimized estimation based on the unbiased distance estimation formulation. In addition, we propose a hypothesis testing approach to adaptively determine the number of dimensions needed to estimate the exact distance with sufficient confidence. We integrate DADE into widely-used AKNN search algorithms, e.g., IVF and HNSW, and conduct extensive experiments to demonstrate the superiority.
• Abstract（参考訳）: 高次元近似$K$近接探索(AKNN)は情報検索を含む様々なアプリケーションの基本課題である。 AKNNの既存のアルゴリズムは、候補生成と距離比較演算(DCO)という2つの主要なコンポーネントに分解することができる。 異なる手法は候補を生成するユニークな方法を持っているが、それらはすべて同じDCOプロセスを共有している。 本研究では,既存のほとんどのAKNNアルゴリズムの時間的コストを支配するDCOのプロセスの高速化に焦点をあてる。 そこで本研究では,DADEと呼ばれる低次元空間の正確な距離を近似するデータ認識距離推定手法を提案する。 理論的には、DADEにおける距離推定がデータ分布の点で不偏であることを証明している。 さらに,不偏距離推定の定式化に基づく最適化された推定法を提案する。 さらに,十分な信頼度で正確な距離を推定するために必要な次元数を適応的に決定する仮説テスト手法を提案する。 DADEを広く使われているAKNN検索アルゴリズム(例えば、IVF、HNSW)に統合し、その優位性を実証するための広範な実験を行う。

関連論文リスト

• RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search [11.069814476661827]
  クロスモーダルANNSは、あるモダリティからデータベクトルを使用して、他のモダリティから最も類似したアイテムを検索することを目的としている。 最先端のANNSアプローチでは、OODワークロードのパフォーマンスが低下している。 本稿では、クエリ分布のガイダンスに基づいて構築された効率的なANNSグラフインデックスであるpRojected bipartite Graph(RoarGraph)を提案する。
  論文  参考訳（メタデータ） (2024-08-16T06:48:16Z)
• Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders [77.84801537608651]
  クエリ-イムペアを共同で符号化することで類似性を計算するクロスエンコーダ(CE)モデルは、クエリ-イム関連性を推定する埋め込みベースモデル(デュアルエンコーダ)よりも優れている。 本稿では,潜時クエリとアイテム埋め込みを効率的に計算してCEスコアを近似し,CE類似度を近似したk-NN探索を行うスパース行列分解法を提案する。
  論文  参考訳（メタデータ） (2024-05-06T17:14:34Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
  微分可能なアーキテクチャサーチ (DARTS) は、NASの高効率性のため、一般的なワンショットパラダイムである。 この作業はゼロオーダーの最適化に変わり、上記の近似を強制せずに探索するための新しいNASスキームであるZARTSを提案する。 特に、12ベンチマークの結果は、DARTSの性能が低下するZARTSの顕著な堅牢性を検証する。
  論文  参考訳（メタデータ） (2021-10-10T09:35:15Z)
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search [8.25574589820305]
  近似近傍近傍近傍(DEANN)からの密度推定アルゴリズムを提案する。 我々は、非バイアス密度推定(KDE)を計算するために、ANNアルゴリズムをブラックボックスサブルーチンとして適用する。 我々の実装は、検討したすべての高次元データセットにおいて、技術実装の状況よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-06T17:11:28Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Nearest Neighbor Search Under Uncertainty [19.225091554227948]
  Nearest Neighbor Search (NNS) は知識表現、学習、推論の中心的なタスクである。 NNSを不確実性(NNSU)下で研究する。
  論文  参考訳（メタデータ） (2021-03-08T20:20:01Z)
• Manifold learning with approximate nearest neighbors [1.8477401359673706]
  多様体学習アルゴリズムでは近距離近傍の近似アルゴリズムを多用し,その埋め込み精度への影響を評価した。 ベンチマークmnistデータセットに基づく徹底的な実証調査により,近似近辺の計算時間が大幅に改善されることが示されている。 本アプリケーションは,提案手法を用いて異常を可視化し,同定し,高次元データ中の基盤構造を明らかにする方法を示す。
  論文  参考訳（メタデータ） (2021-02-22T12:04:23Z)
• Diverse Knowledge Distillation for End-to-End Person Search [81.4926655119318]
  人物検索は、画像ギャラリーから特定の人物をローカライズし識別することを目的としている。 最近の手法は2つのグループ、すなわち2段階とエンドツーエンドのアプローチに分類できる。 ボトルネックを解消するために、多様な知識蒸留を備えたシンプルで強力なエンドツーエンドネットワークを提案します。
  論文  参考訳（メタデータ） (2020-12-21T09:04:27Z)
• DecAug: Augmenting HOI Detection via Decomposition [54.65572599920679]
  現在のアルゴリズムでは、データセット内のトレーニングサンプルやカテゴリの不均衡が不足している。 本稿では,HOI検出のためのDECAugと呼ばれる効率的かつ効率的なデータ拡張手法を提案する。 実験の結果,V-COCOおよびHICODETデータセットの3.3mAPと1.6mAPの改善が得られた。
  論文  参考訳（メタデータ） (2020-10-02T13:59:05Z)
• Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations [21.68175843347951]
  本稿では,ユーザとイテムのインタラクションデータを用いて,検索可能な構造を直接学習するために,Deep Retrieval(DR)を提案する。 DRは、産業レコメンデーションシステムのために数億のアイテムをスケールで展開した最初の非ANNアルゴリズムの1つである。
  論文  参考訳（メタデータ） (2020-07-12T06:23:51Z)

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

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