論文の概要: Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces

• arxiv url: http://arxiv.org/abs/2506.06557v1
• Date: Fri, 06 Jun 2025 22:09:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 16:33:10.328055
• Title: Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces
• Title（参考訳）: Infinity Search:q-metric Spaces上の投影を用いた近似ベクトル探索
• Authors: Antonio Pariente, Ignacio Hounie, Santiago Segarra, Alejandro Ribeiro,
• Abstract要約: 我々は、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を減らすことができることを示した。 任意の異方性測度を持つデータセットを$q$-metric空間に埋め込む新しい射影法を提案する。
• 参考スコア（独自算出の注目度）: 94.12116458306916
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Despite the ubiquity of vector search applications, prevailing search algorithms overlook the metric structure of vector embeddings, treating it as a constraint rather than exploiting its underlying properties. In this paper, we demonstrate that in $q$-metric spaces, metric trees can leverage a stronger version of the triangle inequality to reduce comparisons for exact search. Notably, as $q$ approaches infinity, the search complexity becomes logarithmic. Therefore, we propose a novel projection method that embeds vector datasets with arbitrary dissimilarity measures into $q$-metric spaces while preserving the nearest neighbor. We propose to learn an approximation of this projection to efficiently transform query points to a space where euclidean distances satisfy the desired properties. Our experimental results with text and image vector embeddings show that learning $q$-metric approximations enables classic metric tree algorithms -- which typically underperform with high-dimensional data -- to achieve competitive performance against state-of-the-art search methods.
• Abstract（参考訳）: ベクトル探索の用途が多様であるにもかかわらず、一般的な探索アルゴリズムはベクトル埋め込みの計量構造を見落とし、その基礎となる性質を活かすのではなく、制約として扱う。 本稿では、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を削減できることを示す。 特に$q$が無限大に近づくにつれ、検索の複雑さは対数的になる。 そこで本研究では, 任意の異方性測度を持つベクトルデータセットを, 近接した近傍を保ちながら$q$-metric空間に埋め込む新しいプロジェクション手法を提案する。 本稿では,この射影の近似を学習し,ユークリッド距離が所望の特性を満たすような空間に効率的に問合せ点を変換することを提案する。 テキストと画像ベクトルの埋め込みによる実験結果から、$q$-metric近似の学習により、古典的なメートル法木アルゴリズム(通常は高次元データで劣る)が、最先端の検索手法と競合する性能を達成できることが示された。

関連論文リスト

• Boundary Detection Algorithm Inspired by Locally Linear Embedding [8.259071011958254]
  本稿では,広く使用されている局所的線形埋め込みアルゴリズムにインスパイアされた境界点検出手法を提案する。 本手法は,2つの近傍探索スキーム($epsilon$-radius ball scheme)と$K$-nearest neighbor scheme($K$-nearest neighbor scheme)を用いて実装する。
  論文  参考訳（メタデータ） (2024-06-26T16:05:57Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Weighting vectors for machine learning: numerical harmonic analysis applied to boundary detection [3.8848561367220276]
  距離空間がユークリッド空間であるとき、重み付けベクトルが境界検出の有効なツールであることを示す。 我々は,ベンチマークデータセット上での最先端技術の性能を競争力のある,あるいは超越した性能を示す。
  論文  参考訳（メタデータ） (2021-06-01T22:14:22Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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