論文の概要: Approximate Nearest Neighbor Search with Window Filters

• arxiv url: http://arxiv.org/abs/2402.00943v2
• Date: Tue, 4 Jun 2024 15:38:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 13:17:49.437453
• Title: Approximate Nearest Neighbor Search with Window Filters
• Title（参考訳）: ウィンドウフィルタを用いた近似近傍探索
• Authors: Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, Julian Shun,
• Abstract要約: 我々は、$textitc-approximate window search$: Near Near neighbor search where the dataset each point has anumeric label, and the goal to find Near neighbors to query within any label ranges。 本稿では,従来のc-近似近傍問題の解法を,ウィンドウ探索の解法であるデータ構造に変換するためのモジュラーツリーベースフレームワークを提案し,理論的に解析する。
• 参考スコア（独自算出の注目度）: 6.984859675093657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We define and investigate the problem of $\textit{c-approximate window search}$: approximate nearest neighbor search where each point in the dataset has a numeric label, and the goal is to find nearest neighbors to queries within arbitrary label ranges. Many semantic search problems, such as image and document search with timestamp filters, or product search with cost filters, are natural examples of this problem. We propose and theoretically analyze a modular tree-based framework for transforming an index that solves the traditional c-approximate nearest neighbor problem into a data structure that solves window search. On standard nearest neighbor benchmark datasets equipped with random label values, adversarially constructed embeddings, and image search embeddings with real timestamps, we obtain up to a $75\times$ speedup over existing solutions at the same level of recall.
• Abstract（参考訳）: 我々は、$\textit{c-approximate window search}$: Near Near neighbor search where the dataset each point has anumeric label, and the goal to find Near neighbors to querys within any label ranges。 タイムスタンプフィルタによる画像検索や文書検索,コストフィルタによる製品検索といったセマンティック検索の問題は,この問題の自然な例である。 本稿では,従来のc-近似近傍問題の解法を,ウィンドウ探索の解法であるデータ構造に変換するためのモジュラーツリーベースフレームワークを提案し,理論的に解析する。 ランダムなラベル値、逆向きに構築された埋め込み、およびリアルタイムのタイムスタンプによる画像検索埋め込みを備えた標準的な近接ベンチマークデータセットでは、同じレベルのリコールで既存のソリューションよりも75\times$のスピードアップが得られる。

関連論文リスト

• iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search [24.85572470526277]
  周辺地域を探索するRFANN(Range-filtering Near Near Near Near neighbor)は、学術や産業で注目を集めている。 最近の研究では、可能な全てのクエリ範囲に対して、$O(n2)$専用のグラフベースのインデックスを構築することを提案する。 要素グラフと呼ばれるグラフベースのインデックスを適度な範囲で作成する。
  論文  参考訳（メタデータ） (2024-09-04T09:41:52Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
  論文  参考訳（メタデータ） (2024-05-07T15:57:39Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations [20.944914202453962]
  グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
  論文  参考訳（メタデータ） (2023-10-29T19:25:48Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• 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)
• Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
  グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。 この技術は既知のベンチマークよりも最先端の結果が得られる。
  論文  参考訳（メタデータ） (2021-12-05T19:48:42Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)
• Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms [0.0]
  与えられたクエリポイントのデータセットでk-nearestの隣人を見つける問題は、数年前から解決されてきた。 本稿では,K-Nearest Neighbor Search(K-Nearest Neighbor Search)の手法について,計算の視点から検討する。 本論文では,KNNSアプローチの対敵点に対する堅牢性を評価するために,汎用的な強化学習ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-02-10T16:10:58Z)
• Cross-Domain Generalization Through Memorization: A Study of Nearest Neighbors in Neural Duplicate Question Detection [72.01292864036087]
  重複質問検出(DQD)は,コミュニティの効率向上と自動質問応答システムの実現に重要である。 我々は、DQDのクロスドメイン一般化のために、ニューラル表現を活用し、近接する隣人を研究する。 StackExchange、Spring、Quoraの各データセットの異なるクロスドメインシナリオにおいて、このメソッドの堅牢なパフォーマンスを観察します。
  論文  参考訳（メタデータ） (2020-11-22T19:19:33Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)

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

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