論文の概要: 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)パラメータチューニングは一切必要ありません。 この手法は,クエリと十分に類似した全てのデータベース項目を報告することが重要となる,盗作検出シナリオに特に適している。

関連論文リスト

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

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

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