論文の概要: 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)に統合し、その優位性を実証するための広範な実験を行う。

関連論文リスト

• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Exploiting Pre-trained Models for Drug Target Affinity Prediction with Nearest Neighbors [58.661454334877256]
  薬物-標的結合親和性(DTA)予測は、薬物発見に不可欠である。 DTA予測へのディープラーニング手法の適用にもかかわらず、達成された精度は依然として準最適である。 事前学習したDTA予測モデルに適用した非表現埋め込みに基づく検索手法である$k$NN-DTAを提案する。
  論文  参考訳（メタデータ） (2024-07-21T15:49:05Z)
• A Near-Linear Time Algorithm for the Chamfer Distance [21.018781726524946]
  チャンファー距離は点雲間の相似性の一般的な尺度である。 1+epsilon)$-approximate アルゴリズムは,Chamfer 距離をほぼ直線走行時間で推定する。 我々の実験は、大規模な高次元データセット上では正確かつ高速であることを示した。
  論文  参考訳（メタデータ） (2023-07-06T15:07:48Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Training Robust Deep Models for Time-Series Domain: Novel Algorithms and Theoretical Analysis [32.45387153404849]
  時系列分類タスクのための堅牢なDNNを作成するために,RObust Training for Time-Series (RO-TS) と呼ばれる新しいフレームワークを提案する。 時系列アライメントによる和構造を用いた定式化の一般化と利点を示す。 実世界のベンチマーク実験により, RO-TSは, 対戦型トレーニングと比較して, より堅牢なDNNを生成することが示された。
  論文  参考訳（メタデータ） (2022-07-09T17:21:03Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search [8.25574589820305]
  近似近傍近傍近傍(DEANN)からの密度推定アルゴリズムを提案する。 我々は、非バイアス密度推定(KDE)を計算するために、ANNアルゴリズムをブラックボックスサブルーチンとして適用する。 我々の実装は、検討したすべての高次元データセットにおいて、技術実装の状況よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-06T17:11:28Z)
• Nearest Neighbor Search Under Uncertainty [19.225091554227948]
  Nearest Neighbor Search (NNS) は知識表現、学習、推論の中心的なタスクである。 NNSを不確実性(NNSU)下で研究する。
  論文  参考訳（メタデータ） (2021-03-08T20:20:01Z)
• An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane [3.9596068699962315]
  2-ワッサーシュタイン距離(英: 2-Wasserstein distance、RMS distance)は確率分布間の類似性の有用な尺度である。 我々は$O(n5/4mathrmpolylog n,1/varepsilon)$timeで実行される新しい$varepsilon$-approximationアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-15T14:47:25Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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