論文の概要: 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倍以上の速度アップを達成できることを実験的に証明した。
本稿では,クエリ毎に期待される距離演算数と,一定数のメンバを持つプールがプルーンされる確率に関する理論的解析を行う。
この方法では,他の手法と異なり,非常に有用で実用的な分布特性を活用できる。
我々の方法では、必要なデータ構造はすべて純粋にオフラインで作成されます。
さらに,本手法は,近傍の真の数に対して強い仮定を課さず,データベースに新しいベクトルを動的に追加するストリーミング設定に適応し,パラメータチューニングを必要としない。
関連論文リスト
- pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
埋め込み検索は、クエリとアイテムの両方の共有セマンティック表現空間を学習することを目的としている。
現在の産業実践では、検索システムは典型的には、異なるクエリに対して一定数のアイテムを検索する。
論文 参考訳（メタデータ） (2024-10-25T07:14:12Z) - Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
クラスタリングに基づく最大内部積探索(MIPS)におけるルーティングの問題について検討する。
最大内積を楽観的に推定するために,各シャード内の内積分布のモーメントを組み込んだ新しい枠組みを提案する。
論文 参考訳（メタデータ） (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) - Worst-case Performance of Popular Approximate Nearest Neighbor Search
Implementations: Guarantees and Limitations [20.944914202453962]
グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。
DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。
本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
論文 参考訳（メタデータ） (2023-10-29T19:25:48Z) - Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。
提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
論文 参考訳（メタデータ） (2022-02-22T01:34:35Z) - Approximate Nearest Neighbor Search under Neural Similarity Metric for
Large-Scale Recommendation [20.42993976179691]
本稿では,任意のマッチング関数にANN探索を拡張する新しい手法を提案する。
我々の主な考えは、すべての項目から構築された類似性グラフに一致する関数で、欲張りのウォークを実行することである。
提案手法は,Taobaoのディスプレイ広告プラットフォームに完全に展開されており,広告収入の大幅な増加をもたらす。
論文 参考訳（メタデータ） (2022-02-14T07:55:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。