論文の概要: A Bi-metric Framework for Fast Similarity Search

• arxiv url: http://arxiv.org/abs/2406.02891v1
• Date: Wed, 5 Jun 2024 03:17:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 22:05:49.141833
• Title: A Bi-metric Framework for Fast Similarity Search
• Title（参考訳）: 高速類似検索のためのバイメトリックフレームワーク
• Authors: Haike Xu, Sandeep Silwal, Piotr Indyk,
• Abstract要約: 近接するデータ構造を設計するための新しい「バイメトリック」フレームワークを提案する。 本フレームワークでは, 高精度で計算に費用がかかる基底トラストメトリックと, 安価だが精度の低いプロキシメトリックの2つの相似性関数を仮定する。 プロキシメトリックのみを使用して、両方のメトリクスに対して限られた数の呼び出ししか使用せず、データ構造を構築する方法を示す。
• 参考スコア（独自算出の注目度）: 23.254885582600775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new "bi-metric" framework for designing nearest neighbor data structures. Our framework assumes two dissimilarity functions: a ground-truth metric that is accurate but expensive to compute, and a proxy metric that is cheaper but less accurate. In both theory and practice, we show how to construct data structures using only the proxy metric such that the query procedure achieves the accuracy of the expensive metric, while only using a limited number of calls to both metrics. Our theoretical results instantiate this framework for two popular nearest neighbor search algorithms: DiskANN and Cover Tree. In both cases we show that, as long as the proxy metric used to construct the data structure approximates the ground-truth metric up to a bounded factor, our data structure achieves arbitrarily good approximation guarantees with respect to the ground-truth metric. On the empirical side, we apply the framework to the text retrieval problem with two dissimilarity functions evaluated by ML models with vastly different computational costs. We observe that for almost all data sets in the MTEB benchmark, our approach achieves a considerably better accuracy-efficiency tradeoff than the alternatives, such as re-ranking.
• Abstract（参考訳）: 近接するデータ構造を設計するための新しい「バイメトリック」フレームワークを提案する。 本フレームワークでは, 高精度で計算に費用がかかる基底トラストメトリックと, 安価だが精度の低いプロキシメトリックの2つの相似性関数を仮定する。 理論と実践の両方において,クエリ手順が高価なメトリックの精度を達成するように,プロキシメトリックのみを使用してデータ構造を構築する方法を示す。 我々の理論的結果は、このフレームワークを2つの一般的な近接探索アルゴリズムであるDiskANNとCover Treeのインスタンス化する。 いずれの場合も、データ構造を構成するために使用されるプロキシメトリックが、境界要素まで基底トラスの計量を近似する限り、データ構造は、基底トラスの計量に関して任意に良好な近似を保証する。 実験的な面では、計算コストが大幅に異なるMLモデルにより評価された2つの相似関数を持つテキスト検索問題に対して、このフレームワークを適用した。 MTEBベンチマークのほぼ全てのデータセットに対して、我々の手法は、再ランク付けのような代替手法よりも精度と効率のトレードオフがかなり優れていることを観察する。

関連論文リスト

• Discovering Data Structures: Nearest Neighbor Search and Beyond [18.774836778996544]
  データ構造をエンド・ツー・エンドで学習するための一般的なフレームワークを提案する。 我々のフレームワークは、基礎となるデータ分布に適応し、クエリと空間の複雑さをきめ細やかな制御を提供する。 まず、この枠組みを近接探索問題に適用する。
  論文  参考訳（メタデータ） (2024-11-05T16:50:54Z)
• Are We Really Achieving Better Beyond-Accuracy Performance in Next Basket Recommendation? [57.91114305844153]
  次のバスケットレコメンデーション(NBR)は、ますます注目を集めている特別なタイプのシーケンシャルレコメンデーションである。 NBRに関する最近の研究は、繰り返し項目を推奨することと項目を探索することの間に大きなパフォーマンス差が見つかった。 本稿では,繰り返しアイテムを扱い,個別にアイテムを探索する2段階反復探索フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-05-02T09:59:35Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version] [56.94699829208978]
  本稿では,動的システムのスマートでスケーラブルな抽象化のための適応的洗練手順を提案する。 最適構造を学ぶために、マルコフ連鎖の間のカントロビッチに着想を得た計量を定義する。 本稿では,従来の線形プログラミング手法よりも計算量が多くなることを示す。
  論文  参考訳（メタデータ） (2023-03-30T11:26:40Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  アクティブラーニングフレームワークは、最も有益なデータポイントのラベル付けを積極的に要求することで、データアノテーションのコストを削減することを目的としている。 提案手法には、不確実性に基づく手法、幾何学的手法、不確実性に基づく手法と幾何学的手法の暗黙の組み合わせなどがある。 本稿では, サンプル選択戦略における効率的な探索・探索トレードオフを実現するために, 不確実性に基づくフレームワークと幾何学的フレームワークの両方の最近の進歩を革新的に統合する。 本フレームワークは,(1)正確な後続推定,(2)計算オーバーヘッドと高い精度のトレードオフの2つの利点を提供する。
  論文  参考訳（メタデータ） (2022-10-11T20:20:20Z)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  ニューラルアーキテクチャ探索のための演算寄与度(Shapley-NAS)を評価するためのShapley値に基づく手法を提案する。 提案手法は,光探索コストに比例して最先端の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-20T14:41:49Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies [65.92826041406802]
  本稿では,グラフ分類の観点から,プロキシベースのディープグラフメトリックラーニング手法を提案する。 複数のグローバルプロキシを利用して、各クラスの元のデータポイントを総括的に近似する。 本研究では, 近接関係を接地トラス・ラベルに従って調整する, 新たな逆ラベル伝搬アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-26T14:52:42Z)
• Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion [59.549664231655726]
  ケースベース推論(CBR)システムは,与えられた問題に類似した事例を検索することで,新たな問題を解決する。 本稿では,知識ベース(KB)の推論において,そのようなシステムが実現可能であることを示す。 提案手法は,KB内の類似エンティティからの推論パスを収集することにより,エンティティの属性を予測する。
  論文  参考訳（メタデータ） (2020-10-07T17:48:12Z)
• Robust Similarity and Distance Learning via Decision Forests [8.587164648430251]
  距離学習のための新たな決定森林アルゴリズムを提案し,これをSimisity and Metric Random Forests(SMERF)と呼ぶ。 任意の距離を近似し、重要な特徴を識別する能力は、シミュレーションデータセット上で実証的に実証されている。
  論文  参考訳（メタデータ） (2020-07-27T20:17:42Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)

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

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