論文の概要: SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora
- arxiv url: http://arxiv.org/abs/2602.10908v1
- Date: Wed, 11 Feb 2026 14:40:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-12 21:44:02.012679
- Title: SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora
- Title（参考訳）: SoftMatcha 2: 大規模コーパスのための高速でソフトなパターンマッチング
- Authors: Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi,
- Abstract要約: 超高速でフレキシブルな探索アルゴリズムを提案し,一兆分の1の自然言語コーパスを0.3秒以内で探索する。
提案手法では,コーパスサイズによく適合する接尾辞配列に基づく文字列マッチングを用いる。
提案手法は,既存の手法に比べて検索遅延を著しく低減することを示す。
- 参考スコア（独自算出の注目度）: 13.87355367137306
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while handling semantic variations (substitution, insertion, and deletion). Our approach employs string matching based on suffix arrays that scales well with corpus size. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: fast exact lookup enabled by a disk-aware design, and dynamic corpus-aware pruning. We theoretically show that the proposed method suppresses exponential growth in the search space with respect to query length by leveraging statistical properties of natural language. In experiments on FineWeb-Edu (Lozhkov et al., 2024) (1.4T tokens), we show that our method achieves significantly lower search latency than existing methods: infini-gram (Liu et al., 2024), infini-gram mini (Xu et al., 2025), and SoftMatcha (Deguchi et al., 2025). As a practical application, we demonstrate that our method identifies benchmark contamination in training corpora, unidentified by existing approaches. We also provide an online demo of fast, soft search across corpora in seven languages.
- Abstract（参考訳）: 意味的変動(置換,挿入,削除)を処理しながら,数兆スケールの自然言語コーパスを0.3秒以内で探索できる超高速で柔軟な探索アルゴリズムを提案する。
提案手法では,コーパスサイズによく適合する接尾辞配列に基づく文字列マッチングを用いる。
クエリのセマンティック・リラクゼーションによって引き起こされる組合せ的爆発を緩和するため,本手法は,ディスク・アウェア・デザインによって実現された高速かつ正確なルックアップと動的コーパス・アウェア・プルーニングという2つの重要なアルゴリズムに基づく。
提案手法は,自然言語の統計的特性を利用して,クエリ長に対する探索空間の指数的増加を抑制することを理論的に示す。
Infini-gram (Liu et al , 2024), infini-gram mini (Xu et al , 2025), SoftMatcha (Deguchi et al , 2025),。
実例として,本手法は既存の手法で同定されていないコーパスのベンチマーク汚染を識別することを示した。
また、7つの言語でコーパスを横断する高速でソフトな検索のオンラインデモも提供しています。
関連論文リスト
- Beyond Magic Words: Sharpness-Aware Prompt Evolving for Robust Large Language Models with TARE [57.67972800581953]
そこで,本論文では,プロンプトをハードパラフレーズで強調する内的,サンプリングに基づく逆探索を交互に行う,デリバティブフリーなフレームワークTAREを紹介する。
また,意味的近傍を形成するために異方性重みを学習し,時間とともに半径を調整し,探索と忠実性のバランスをとるATAREを提案する。
論文 参考訳（メタデータ） (2025-09-28T23:57:05Z) - SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches [5.80278230280824]
本稿では,単語埋め込みと曲面レベルのマッチングを緩和することにより,意味的かつ効率的なパターンマッチングを実現する新しいアルゴリズムを提案する。
提案手法は,数十億のコーパスを1秒以内で探索できることを実証した。
論文 参考訳（メタデータ） (2025-03-05T17:53:11Z) - A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。
本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。
第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
論文 参考訳（メタデータ） (2024-07-17T21:26:27Z) - Efficient Inverted Indexes for Approximate Retrieval over Learned Sparse Representations [8.796275989527054]
本稿では,学習したスパース埋め込みを高速に検索できる逆インデックスの新たな組織を提案する。
提案手法では,逆リストを幾何学的に結合したブロックに整理し,それぞれに要約ベクトルを備える。
以上の結果から, 地震動は, 最先端の逆インデックスベースソリューションよりも1～2桁高速であることが示唆された。
論文 参考訳（メタデータ） (2024-04-29T15:49:27Z) - Stream of Search (SoS): Learning to Search in Language [29.841835308845948]
本稿では,言語における探索の過程をフラットな文字列として表現することで,言語モデルがどのように学習するかを示す。
本稿では,複数のシンボル検索戦略を抽出する統一言語を提案する。
この結果から,言語モデルでは,探索による問題解決や,異なる探索戦略を柔軟に活用する自己改善,新たな探索手法の発見などが可能であることが示唆された。
論文 参考訳（メタデータ） (2024-04-01T06:50:52Z) - Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。
私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。
ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
論文 参考訳（メタデータ） (2023-02-10T18:50:37Z) - Bridging the Training-Inference Gap for Dense Phrase Retrieval [104.4836127502683]
密度の高いレトリバーを構築するには、トレーニングやニューラルネットワークの検証など、一連の標準手順が必要である。
本稿では,高密度検索におけるトレーニングと推論のギャップを減らせる方法について検討する。
コーパス全体の小さな部分集合を用いて高密度レトリバーを効率よく検証する方法を提案する。
論文 参考訳（メタデータ） (2022-10-25T00:53:06Z) - GOLD-NAS: Gradual, One-Level, Differentiable [100.12492801459105]
GOLD-NAS (Gradual One-Level Differentiable Neural Architecture Search) という新しいアルゴリズムを提案する。
1レベル最適化に可変リソース制約を導入し、弱い演算子をスーパーネットワークから徐々に追い出す。
論文 参考訳（メタデータ） (2020-07-07T10:37:49Z) - Interactive Extractive Search over Biomedical Corpora [41.72755714431404]
本稿では,生命科学研究者が言語的に注釈付けされたテキストのコーパスを検索できるようにするシステムを提案する。
本稿では,下層の言語表現の詳細を知る必要のない軽量なクエリ言語を提案する。
探索は,効率的な言語グラフインデクシングと検索エンジンにより,対話的な速度で行われる。
論文 参考訳（メタデータ） (2020-06-07T13:26:32Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Progressively Pretrained Dense Corpus Index for Open-Domain Question
Answering [87.32442219333046]
本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。
本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
論文 参考訳（メタデータ） (2020-04-30T18:09:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。