論文の概要: Panache: One-Pass Motif Discovery at Every Window Length

• arxiv url: http://arxiv.org/abs/2607.17481v1
• Date: Mon, 20 Jul 2026 02:06:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.478004
• Title: Panache: One-Pass Motif Discovery at Every Window Length
• Title（参考訳）: パナチ:窓の長所1つ1つ1つのモチフ発見
• Authors: Tej Sanibh Ranade,
• Abstract要約: 我々は、z正規化PMPモチーフ発見のための最初のワンパスストリーミングアルゴリズムであるPanacheを紹介する。 連続するセルフジョイントを、ランタイムが直列の長さでほぼ直線である単一のスキャンに置き換える。 Panacheは1回のパスを2.9分で完了し、正確なモチーフを6.0分で出力する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motif discovery, the search for recurring patterns within a time series, is a core primitive of exploratory data analysis. A pattern, however, is defined by its duration, which analysts rarely know in advance. To resolve this unknown duration, an interval of window lengths is defined, and the accepted method is to try every length in that interval. Existing pan matrix profile (PMP) methods compute one z-normalized matrix profile per length, so $L$ lengths cost $L$ quadratic self-joins over the same series. We introduce Panache, to our knowledge the first one-pass streaming algorithm for z-normalized PMP motif discovery. It replaces the repeated self-joins with a single scan whose runtime is near-linear in the series length. The key observation is that mean-centering a subsequence changes only its DC Fourier coefficient, so the non-DC spectrum of every z-normalized subsequence can be maintained online by sliding-DFT recurrences and running statistics. This spectral state is the key under which similar subsequences collide in an occupancy-controlled hash directory and, through Parseval's theorem, yields a lower bound that rejects most colliding pairs before any exact computation. Panache computes every data-dependent parameter itself, leaving only a resource budget to tune. At the default budget, it recovers all top-20 pan-motifs against exact fixed-exclusion ground truth on 17 UCR configurations, and is faster than every CPU and GPU baseline benchmarked in this paper. On Wafer at five million samples over 51 lengths, Panache completes one pass in 2.9 minutes and emits the exact motifs in 6.0 minutes, against 7.95 hours for the fastest exact CPU baseline and 38.3 minutes for SCAMP on an H100 GPU.
• Abstract（参考訳）: 時系列内の繰り返しパターンを探索するMotif Discoveryは、探索データ分析のコアプリミティブである。 しかし、パターンはその期間によって定義され、アナリストが事前に知ることはめったにない。 この未知の期間を解決するために、ウィンドウ長の間隔を定義し、その間隔で全ての長さを試すことができる。 既存のパン行列プロファイル (PMP) 法は、長さ当たりの z-正規化行列プロファイルを1つ計算するので、$L$長は同級数に対して$L$二次自己接合を行う。 我々は、z正規化PMPモチーフ発見のための最初のワンパスストリーミングアルゴリズムであるPanacheを紹介した。 連続するセルフジョイントを、ランタイムが直列の長さでほぼ直線である単一のスキャンに置き換える。 キーとなる観察は、平均中心のサブシーケンスはそのDCフーリエ係数だけを変えるため、すべてのz正規化サブシーケンスの非DCスペクトルは、スライディングDFT繰り返しと実行統計によってオンラインに維持できるということである。 このスペクトル状態は、類似の列が占有制御されたハッシュディレクトリで衝突する鍵であり、Parsevalの定理により、正確な計算の前にほとんどの衝突ペアを拒否する下界が得られる。 Panacheはすべてのデータ依存パラメータを計算し、調整するリソース予算だけを残します。 デフォルトの予算では、17UCR構成の正確な固定排他的真実に対してトップ20のパンモチーフをすべて回収し、この論文でベンチマークされたすべてのCPUやGPUベースラインよりも高速である。 Waferでは51以上の500万のサンプルを処理し、パナッシュは1回のパスを2.9分で完了し、正確なモチーフを6.0分で出力し、高速なCPUベースラインでは7.95時間、H100 GPUでは38.3分である。

関連論文リスト

• Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling [55.388363730120325]
  本研究では,CTMC(Continuous-Time Markov Chain)フレームワークにおいて,離散拡散を吸収するための$-leapingアルゴリズムを並列化する。 我々は,$$-leapingアルゴリズムとPicard法の連続時間積分形式を利用して,並列時間サンプリング高速化を実現する。 本研究は, 分子構造や言語生成などの応用において, 効率的な並列推論のための離散拡散モデルの可能性を広げるものである。
  論文  参考訳（メタデータ） (2026-07-01T10:59:33Z)
• CART: Context-Anchored Recurrent Transformer -- A Parameter-Efficient Architecture with Learned Stability [0.0]
  CART(Context-Anchored Recurrent Transformer)は、パラメータ効率のよい言語モデルで、1つの共有コアブロックをR倍の深さで再利用する。 我々は1つのコンシューマGPU上でCARTを2段階に分けて評価した: 64-configuration screen at 3,000 steps, then 36 configurations (P=6, R in 6,8,10, three seed) training for 30500 steps (1B tokens)。 256,512,768,1024: 事前深さPはループ数Rを支配し、Rのステージ1ランクはフルトレーニング時に逆になる(R=6は最高になる)。
  論文  参考訳（メタデータ） (2026-05-31T23:26:27Z)
• dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
  拡散大言語モデル(dLLM)は並列トークン予測と低推論遅延を提供する。 既存のオープンソースモデルは、パフォーマンスを確保するためにトークン長のデコードステップをほとんど必要としています。 高速サンプリングのためにdLLMs固有の並列性を解き放つシンプルで効果的な方法であるdParallelを導入する。
  論文  参考訳（メタデータ） (2025-09-30T16:32:52Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。 我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
  論文  参考訳（メタデータ） (2025-06-15T05:50:05Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSMは$textitnon-linear$リカレントモデルで、現在の線形状態空間層と同じくらい高速に長いシーケンスを処理する。 ヤコビ行列を対角線に強制することにより、全列を並列に解くことができる。 LrcSSMは、Liquid-S4のような他の入力変化系が提供しないことを保証する形式的な勾配安定性を提供する。
  論文  参考訳（メタデータ） (2025-05-27T20:02:59Z)
• Matrix Profile for Anomaly Detection on Multidimensional Time Series [34.46977784156833]
  マトリックスプロファイル(MP)は時系列異常検出(TSAD)に有効であることが示されている 本稿では,多次元時系列における異常検出の問題について述べる。 119個の多次元TSADデータセット上で,多次元MPを19個のベースライン法と比較した。
  論文  参考訳（メタデータ） (2024-09-14T04:22:45Z)
• BayOTIDE: Bayesian Online Multivariate Time series Imputation with functional decomposition [31.096125530322933]
  交通やエネルギーといった現実のシナリオでは、値やノイズが欠けている巨大な時系列データが広く観測され、不規則にサンプリングされる。 多くの計算法が提案されているが、そのほとんどは局所的な地平線で動作する。 ほとんど全ての手法は、観測は通常のタイムスタンプでサンプリングされ、複雑な不規則なサンプル時系列を扱うことができないと仮定する。
  論文  参考訳（メタデータ） (2023-08-28T21:17:12Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)

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

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