論文の概要: Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection

• arxiv url: http://arxiv.org/abs/2311.02573v2
• Date: Sat, 7 Sep 2024 03:12:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-11 03:52:53.322501
• Title: Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection
• Title（参考訳）: プラジアリズム検出のための高精度かつ効率的な近接探索のための群検定
• Authors: Harsh Shah, Kashish Mittal, Ajit Rajwade,
• Abstract要約: 本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
• 参考スコア（独自算出の注目度）: 2.3814052021083354
• 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. Our method efficiently marks each item in a database as neighbor or non-neighbor of a query point, based on a cosine distance threshold without exhaustive search. Like other methods for large scale retrieval, our approach exploits the assumption that most of the items in the database are unrelated to the query. However, 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 a multi-stage adaptive group testing algorithm based on binary splitting, we divide 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 show that, using softmax-based features, our method achieves a more than ten-fold speed-up over exhaustive search with no loss of accuracy, on a variety of large datasets. Based on empirically verified models for the distribution of cosine distances, we present a theoretical analysis of the expected number of distance computations per query and the probability that a pool will be pruned. Our method has the following features: (i) It implicitly exploits useful distributional properties of cosine distances unlike other methods; (ii) All required data structures are created purely offline; (iii) It does not impose any strong assumptions on the number of true near neighbors; (iv) It is adaptable to streaming settings where new vectors are dynamically added to the database; and (v) It does not require any parameter tuning. The high recall of our technique makes it particularly suited to plagiarism detection scenarios where it is important to report every database item that is sufficiently similar item to the query.
• Abstract（参考訳）: 本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 大規模検索の他の方法と同様に、我々の手法は、データベース内のほとんどの項目がクエリと無関係であるという仮定を利用する。 しかし、クエリベクトルのコサイン類似性は、最も関係の低い隣人と、非隣人でない隣人との間に大きな違いは生じない。 バイナリ分割に基づく多段階適応型グループテストアルゴリズムに従い、各ステップで検索対象の項目の集合を半分に分割し、より小さなサブセットでドット製品テストを行う。 本手法は,ソフトマックスに基づく特徴量を用いて,様々な大規模データセットを用いて,完全探索よりも10倍以上の高速化を実現していることを示す。 実験により検証されたコサイン距離分布モデルに基づいて,クエリ毎の距離計算の期待数と,プールが刈り取られる確率を理論的に解析する。 我々の手法には以下の特徴がある。 (i)他の方法と異なり、コサイン距離の有用な分布特性を暗黙的に活用する。 (ii) 必要なデータ構造はすべて、純粋にオフラインで作成されます。 三 隣人の実数について強い前提を課さないこと。 (iv)データベースに新しいベクターを動的に追加するストリーミング設定に適応し、 (v)パラメータチューニングは一切必要ありません。 この手法は,クエリと十分に類似した全てのデータベース項目を報告することが重要となる,盗作検出シナリオに特に適している。

関連論文リスト

• 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)

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

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