論文の概要: CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees

• arxiv url: http://arxiv.org/abs/2610.05330v1
• Date: Sun, 04 Oct 2026 15:53:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 21:34:04.594787
• Title: CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees
• Title（参考訳）: CT-Miner:カルテジアンツリーによる高速で粗い時系列パターンマイニング
• Abstract要約: 時系列は、しばしば繰り返し発生する構造パターンを含み、そのようなパターンをコンパクトな表現に効率的にマイニングすることは、長いシーケンスのスケーラブルな解析に不可欠である。 我々は,CT等価サブシーケンスをコンパクトに整理し,共有構造情報を再利用する,カルテシアン接尾辞木に基づく新しいカルテシアンパターンマイニングアルゴリズムを提案する。 本手法はCT-パターンの総括収集を$O(n4)$から$O(n2)$ timeに削減し,その正確さと複雑性の境界を正式に証明する。
• 参考スコア（独自算出の注目度）: 8.937187963386387
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Time series often contain recurring structural patterns, and efficiently mining such patterns into compact representations is essential for scalable analysis of long sequences. Cartesian tree (CT) equivalence provides a well-established structural abstraction that preserves hierarchical order structure while discarding exact values and fine-grained ordinal variations. By grouping multiple ordinal patterns into a shared structural form, CT equivalence offers a principled way to compress recurring temporal structure. However, mining frequent CT-equivalent patterns at scale remains computationally expensive. A naive pairwise approach repeatedly constructs and counts CT representations over subsequences, requiring $O(n^4)$ time for a sequence of length $n$, which severely limits its applicability to long sequences. We propose a new Cartesian pattern mining algorithm based on a Cartesian suffix tree that compactly organizes CT-equivalent subsequences and reuses shared structural information. Our method reduces exhaustive CT-pattern occurrence collection from $O(n^4)$ to $O(n^2)$ time, and we formally prove the correctness and complexity bounds. We further show that this computational gain translates into effective compact representations. Across diverse time-series datasets, a small set of mined CT patterns preserves meaningful clustering structure, and comparisons with finer-grained order-preserving representations show that CT equivalence reduces redundant ordinal distinctions under limited feature budgets. Our implementation is available at https://github.com/hyundong98/CT-Miner .
• Abstract（参考訳）: 時系列は、しばしば繰り返し発生する構造パターンを含み、そのようなパターンをコンパクトな表現に効率的にマイニングすることは、長いシーケンスのスケーラブルな解析に不可欠である。 カルテシアンツリー(CT)同値性は、正確な値と微粒な順序変化を捨てつつ、階層的な順序構造を保存する、しっかりと確立された構造的抽象化を提供する。 複数の順序パターンを共有構造形式にまとめることで、CT同値性は、繰り返し発生する時間構造を圧縮する原則的な方法を提供する。 しかし、大規模なCT等価パターンのマイニングには計算コストがかかる。 単純なペアワイズアプローチは、サブシーケンス上でCT表現を繰り返し構成し、カウントし、長さ$n$のシーケンスに対して$O(n^4)$時間を必要とする。 我々は,CT等価サブシーケンスをコンパクトに整理し,共有構造情報を再利用する,カルテシアン接尾辞木に基づく新しいカルテシアンパターンマイニングアルゴリズムを提案する。 本手法はCT-パターンの総括収集を$O(n^4)$から$O(n^2)$ timeに削減し,その正確さと複雑性の限界を正式に証明する。 さらに、この計算ゲインが効率的なコンパクト表現に変換されることを示す。 多様な時系列データセット全体にわたって,少量のマイニングCTパターンは有意義なクラスタリング構造を保ち,よりきめ細かい順序保存表現との比較により,CT同値性は限られた特徴予算の下で冗長な順序の区別を減少させることが示された。 私たちの実装はhttps://github.com/hyundong98/CT-Minerで利用可能です。

関連論文リスト

• Learning to Tessellate: Point Cloud Generation via Recursive Spectral Partitioning [58.130498928480456]
  本稿では, トポロジ保存型テッセルレーションプロセスとして, 点雲生成を再構成する自己回帰フレームワークであるPointRSPを提案する。 PointRSPは、複雑な3Dトポロジーをまたいだ強力な一般化を証明し、世代品質と多様性の最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2026-08-03T16:11:43Z)
• RiboSphere: Learning Unified and Efficient Representations of RNA Structures [57.40815107640066]
  RNAのバックボーンは非常に柔軟で、非カノニカル相互作用が一般的であり、実験的に決定された3D構造は比較的少ない。 本稿では,ベクトル量子化とフローマッチングを組み合わせることで,RNAの固有な幾何学的表現を学習するフレームワークであるemphRiboSphereを紹介する。
  論文  参考訳（メタデータ） (2026-03-20T04:36:35Z)
• On the Exact Algorithmic Extraction of Finite Tesselations Through Prime Extraction of Minimal Representative Forms [0.764671395172401]
  本稿では,有限平面格子における正確なテッセルレーションを発見する階層的アルゴリズムを用いる。 グリッドサイズのスケーラビリティを2×2から32×32に評価し,単純な繰り返しタイルの重なり検出が1ms以下の処理時間を示すことを示した。 このアルゴリズムは、正確な軸方向の長方形のテッセルレーションに対して決定論的挙動を提供する。
  論文  参考訳（メタデータ） (2026-03-01T04:20:06Z)
• TimeMar: Multi-Scale Autoregressive Modeling for Unconditional Time Series Generation [11.455232661227313]
  時系列のための構造不整合型マルチスケール生成フレームワークを提案する。 提案手法は,複数の時間分解能において,シーケンスを離散トークンに符号化する。 提案手法は,既存の手法よりも高品質な時系列を生成することを示す。
  論文  参考訳（メタデータ） (2026-01-16T11:00:05Z)
• REWA: A General Theory of Witness-Based Similarity [0.0]
  我々は、すべての離散的、連続的、代数的、学習的類似性を仮定する類似性保存符号化のための普遍的な枠組みを提案する。 この統合により、ブルームフィルタ、Locality Sensitive Hashing (LSH)、Count-Minのスケッチ、ランダムフーリエ機能、Transformerのアテンションカーネルは同じメカニズムのインスタンスであることが分かる。
  論文  参考訳（メタデータ） (2025-11-25T07:04:44Z)
• Learning Discrete Bayesian Networks with Hierarchical Dirichlet Shrinkage [52.914168158222765]
  我々はDBNを学習するための包括的なベイズ的フレームワークについて詳述する。 我々は、並列ランゲヴィン提案を用いてマルコフ連鎖モンテカルロ(MCMC)アルゴリズムを新たに提案し、正確な後続サンプルを生成する。 原発性乳癌検体から予後ネットワーク構造を明らかにするために本手法を適用した。
  論文  参考訳（メタデータ） (2025-09-16T17:24:35Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Interpretable Sequence Clustering [3.280979689839737]
  我々は、ISCT(Interpretable Sequence Clustering Tree)と呼ばれる手法を提案する。 ISCTは、k個のクラスタに対応するk個のリーフノードを生成し、各クラスタの生成方法に関する直感的な説明を提供する。 実世界の14のデータセットに対する実験結果から,本手法が解釈可能な木構造を提供することが示された。
  論文  参考訳（メタデータ） (2023-09-03T11:31:44Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  大規模時間グラフにおける時間的モチーフを正確にカウントするための拡張性のある並列フレームワークを提案する。 提案手法に基づいて,ノード間並列戦略とノード内並列戦略の両方を特徴とする階層型並列フレームワークを設計する。 16の実世界の時間グラフデータセットに対する実験により,提案フレームワークの優位性と性能が示された。
  論文  参考訳（メタデータ） (2022-04-20T05:41:38Z)
• Temporally-Consistent Surface Reconstruction using Metrically-Consistent Atlases [131.50372468579067]
  そこで本稿では,時間変化点雲列から時間一貫性のある面列を復元する手法を提案する。 我々は、再構成された表面をニューラルネットワークによって計算されたアトラスとして表現し、フレーム間の対応性を確立することができる。 当社のアプローチは、いくつかの挑戦的なデータセットにおいて、最先端のものよりも優れています。
  論文  参考訳（メタデータ） (2021-11-12T17:48:25Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  特徴相互作用の効率的なモデリングは、非順序的タスクに対する教師あり学習の基盤となる。 この問題を緩和するため、モデルパラメータをテンソルとして暗黙的に表現することが提案されている。 表現性を向上するため,任意の高次元特徴ベクトルに特徴写像を適用できるようにフレームワークを一般化する。
  論文  参考訳（メタデータ） (2020-01-27T22:38:40Z)

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

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