論文の概要: Group Testing for Accurate and Efficient Range-Based Near Neighbor
Search : An Adaptive Binary Splitting Approach
- arxiv url: http://arxiv.org/abs/2311.02573v1
- Date: Sun, 5 Nov 2023 06:12:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 17:08:30.387273
- Title: Group Testing for Accurate and Efficient Range-Based Near Neighbor
Search : An Adaptive Binary Splitting Approach
- Title（参考訳）: 精度・効率的近傍探索のためのグループテスト : 適応二分法アプローチ
- Authors: Kashish Mittal, Harsh Shah, Ajit Rajwade
- Abstract要約: 本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。
提案手法は, 網羅探索と同一の精度で10以上の係数で, 網羅探索を高速化することを示す。
- 参考スコア（独自算出の注目度）: 2.6764607949560593
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work presents an adaptive group testing framework for the range-based
high dimensional near neighbor search problem. The proposed method detects
high-similarity vectors from an extensive collection of high dimensional
vectors, where each vector represents an image descriptor. Our method
efficiently marks each item in the collection as neighbor or non-neighbor on
the basis of a cosine distance threshold without exhaustive search. Like other
methods in the domain of large scale retrieval, our approach exploits the
assumption that most of the items in the collection are unrelated to the query.
Unlike other methods, it does not assume a large difference between the cosine
similarity of the query vector with the least related neighbor and that with
the least unrelated non-neighbor. Following the procedure of binary splitting,
a multi-stage adaptive group testing algorithm, we split the set of items to be
searched into half at each step, and perform dot product tests on smaller and
smaller subsets, many of which we are able to prune away. We experimentally
show that our method achieves a speed-up over exhaustive search by a factor of
more than ten with an accuracy same as that of exhaustive search, on a variety
of large datasets. We present a theoretical analysis of the expected number of
distance computations per query and the probability that a pool with a certain
number of members will be pruned. In this way, our method exploits very useful
and practical distributional properties unlike other methods. In our method,
all required data structures are created purely offline. Moreover, our method
does not impose any strong assumptions on the number of true near neighbors, is
adaptible to streaming settings where new vectors are dynamically added to the
database, and does not require any parameter tuning.
- Abstract（参考訳）: 本稿では,レンジベース高次元近傍探索問題に対する適応型グループテストフレームワークを提案する。
提案手法では,各ベクトルが画像記述子を表す高次元ベクトルの集合から高相似性ベクトルを検出する。
本手法は,収集中の各項目を,余分な探索をすることなく,コサイン距離閾値に基づいて,隣接または非ニアボーとして効率的にマークする。
大規模検索の分野における他の方法と同様に、我々の手法は、コレクションのほとんどの項目がクエリとは無関係であるという仮定を利用する。
他の方法とは異なり、クエリベクトルのコサイン類似性は、最も関係の低い隣人と、非隣人でない隣人との間に大きな違いを仮定しない。
多段階適応型グループテストアルゴリズムであるbinary splitの手順に従い、各ステップで検索すべき項目のセットを半分に分割し、より小さく小さなサブセットでドット製品テストを行い、その多くが回避できるようになりました。
提案手法は,様々な大規模データセットにおいて,徹底探索と同等の精度で10倍以上の速度アップを達成できることを実験的に証明した。
本稿では,クエリ毎に期待される距離演算数と,一定数のメンバを持つプールがプルーンされる確率に関する理論的解析を行う。
この方法では,他の手法と異なり,非常に有用で実用的な分布特性を活用できる。
我々の方法では、必要なデータ構造はすべて純粋にオフラインで作成されます。
さらに,本手法は,近傍の真の数に対して強い仮定を課さず,データベースに新しいベクトルを動的に追加するストリーミング設定に適応し,パラメータチューニングを必要としない。
関連論文リスト
- A Query-Driven Approach to Space-Efficient Range Searching [12.760453906939446]
クエリのほぼ直線的なサンプルは、クエリ中に訪れたノード数がほぼ最適であるパーティションツリーを構築することができることを示す。
我々は、ノード処理を分類問題として扱い、浅いニューラルネットワークのような高速な分類器を活用して、実験的に効率的なクエリ時間を得ることにより、このアプローチを強化する。
我々のアルゴリズムは,クエリのサンプルに基づいて,セパレータに関連付けられたノードを持つバランスのとれたツリーを構築し,クエリの待ち行列を最小化する。
論文 参考訳（メタデータ） (2025-02-19T12:01:00Z) - Range Retrieval with Graph-Based Indices [0.0]
高次元ベクトル空間における近接点の検索は,情報検索における重要なステップである。
本稿では,グラフに基づくベクトル指標を用いた範囲探索アルゴリズムを提案する。
単純なベースラインアプローチよりも,クエリスループットが最大100倍,平均で5～10倍,パフォーマンスが最大1億データポイントまで向上しています。
論文 参考訳（メタデータ） (2025-02-18T19:18:01Z) - Learning Cluster Representatives for Approximate Nearest Neighbor Search [0.0]
この論文はクラスタリングに基づく近似近傍探索の包括的説明を提供する。
また、新しい最先端の手法のあらゆる側面を紹介し、掘り下げます。
この直感の発達と,それを内積探索の最大化に適用することにより,単純な線形関数を用いた学習クラスタ代表がクラスタリングに基づく近接探索の精度を大幅に向上させることを示した。
論文 参考訳（メタデータ） (2024-12-08T12:31:32Z) - Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
この研究は、クラスタリングに基づく最大内部積探索におけるルーティングを研究することによってギャップを埋める。
各シャード内の内積分布のモーメントを組み込んで最大内積を推定する枠組みを提案する。
論文 参考訳（メタデータ） (2024-05-20T17:47:18Z) - Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders [77.84801537608651]
クエリ-イムペアを共同で符号化することで類似性を計算するクロスエンコーダ(CE)モデルは、クエリ-イム関連性を推定する埋め込みベースモデル(デュアルエンコーダ)よりも優れている。
本稿では,潜時クエリとアイテム埋め込みを効率的に計算してCEスコアを近似し,CE類似度を近似したk-NN探索を行うスパース行列分解法を提案する。
論文 参考訳（メタデータ） (2024-05-06T17:14:34Z) - Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。
提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
論文 参考訳（メタデータ） (2022-02-22T01:34:35Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳（メタデータ） (2021-12-06T20:34:55Z) - Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。
この技術は既知のベンチマークよりも最先端の結果が得られる。
論文 参考訳（メタデータ） (2021-12-05T19:48:42Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。