論文の概要: Scalable Maximal Frequent Episode Mining with Desbordante
- arxiv url: http://arxiv.org/abs/2607.03188v1
- Date: Fri, 03 Jul 2026 10:47:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-07 22:26:29.548856
- Title: Scalable Maximal Frequent Episode Mining with Desbordante
- Title（参考訳）: Desbordanteを用いた拡張型最大周波エピソードマイニング
- Abstract要約: エピソードマイニング(英: Episode mining)は、特定の特徴を持つ出来事のサブシーケンスを抽出し、ユーザにとって価値のある事実を構成することを目的としている。
この問題の最先端は、可能なサブシーケンスを列挙するMaxFEMアルゴリズムである。
本稿では,この問題に対して高い性能のアルゴリズムを設計する取り組みについて述べる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Episode mining aims to extract subsequences of events that possess certain distinctive properties and constitute facts valuable to the user. Maximal frequent episode mining concentrates on discovery of frequently-appearing subsequences, which are not included into any other larger frequent subsequence. The state-of-the-art for this problem is the MaxFEM algorithm which enumerates possible subsequences, while applying various pruning techniques to accelerate the search. However, this is a computationally-intensive problem: reducing the minimum number of required subsequence occurrences or increasing the length of the subsequence both substantially raise running time, which limits practical use of MaxFEM. In this paper we describe our efforts in designing a high-performing algorithm for this problem. For this we: 1) develop an efficient C++ implementation of MaxFEM, and 2) devise an efficient technique to parallelizing it. As the result, we propose an improved parallel MaxFEM variant, which we call ParMaxFEM. Additionally, we integrate the improved algorithm into Desbordante - a high-performance, open-source data profiler with deep Python integration that treats patterns as first-class entities and allows users to develop their custom programs that can include discovery and validation of patterns. To evaluate our approach we compare both C++ implementations with the original SPMF implementation. Experiments demonstrated that our reimplemented version provides up to $8\times$ speedup over the SPMF baseline, while our parallelization technique provides up to $35\times$ improvement overall (on 8 cores).
- Abstract（参考訳）: エピソードマイニング(英: Episode mining)は、特定の特徴を持つ出来事のサブシーケンスを抽出し、ユーザにとって価値のある事実を構成することを目的としている。
最大頻度のエピソードマイニングは、他の大きな頻出サブシークエンスには含まれない頻出サブシークエンスの発見に集中している。
この問題の最先端は、検索を高速化するために様々なプルーニング技術を適用しながら、可能な列を列挙するMaxFEMアルゴリズムである。
しかし、これは計算集約的な問題であり、必要となるサブシークエンスの発生を最小限に減らしたり、サブシークエンスの長さを長くすると実行時間が大幅に増加し、MaxFEMの実用的使用が制限される。
本稿では,この問題に対して高い性能のアルゴリズムを設計する取り組みについて述べる。
このために、
1) MaxFEMの効率的なC++実装を開発し、
2) 並列化のための効率的な手法を考案する。
その結果、ParMaxFEMと呼ばれる改良された並列MaxFEM変異体を提案する。
さらに、改良されたアルゴリズムをDesbordanteに統合します。Desbordante - 高度なPython統合を備えた高性能でオープンソースのデータプロファイラで、パターンを第一級エンティティとして扱い、ユーザがパターンの発見と検証を含むカスタムプログラムを開発することができます。
このアプローチを評価するために、C++実装と元のSPMF実装を比較した。
実験では、再実装されたバージョンは、SPMFベースラインを最大8ドル、並列化技術は、全体的な(8コアで)最大35ドルです。
関連論文リスト
- Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
フェデレーション行列の2レベル最適化は、機械学習に広く応用されているため、近年積極的に研究されている。
既存のフェデレートされた双レベル最適化アルゴリズムは、二階ヘッセン行列とヤコビ行列の計算を必要とする。
本稿では,一階オーラクルのみに依存する新しいフェデレーション収束分散誘導二段降下アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-14T21:12:59Z) - AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。
具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。
これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
論文 参考訳（メタデータ） (2024-03-06T15:06:11Z) - HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
高実用性シーケンシャルパターンマイニング (HUSPM) が重要視されている。
シークエンスプロジェクション(seqPro)と呼ばれるコンパクトな構造を設計し、シークエンスプロ構造(HUSP-SP)を用いた効率的なアルゴリズムを提案する。
HUSP-SPは, 実行時間, メモリ使用量, 検索空間のプルーニング効率, スケーラビリティにおいて, 最先端のアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2022-12-29T10:56:17Z) - Efficient Algorithms for Extreme Bandits [20.68824391770909]
我々は,学習者が最大の報酬を集めようとするマルチアーマッド・バンディットの変種であるExtreme Bandit問題に貢献する。
まず、報酬分布の尾部における軽度の仮定の下で、i.d確率変数の最大値の濃度について検討する。
次に,より適応性の高いQoMax-SDAアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-03-21T11:09:34Z) - Min-Max Bilevel Multi-objective Optimization with Applications in
Machine Learning [30.25074797092709]
本稿では,min-maxバイレベル多目的最適化フレームワークを提案する。
表現学習と超目的学習の応用を強調している。
論文 参考訳（メタデータ） (2022-03-03T18:56:13Z) - TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
本稿では,高速CM-SPAMアルゴリズムに基づく汎用フレームワークTaSPMを提案する。
また,マイニングプロセスにおける無意味な操作を減らすために,いくつかのプルーニング戦略を提案する。
実験の結果,新たなターゲットマイニングアルゴリズムであるTaSPMは実行時間を短縮し,メモリ消費を低減できることがわかった。
論文 参考訳（メタデータ） (2022-02-26T17:49:47Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳（メタデータ） (2020-04-16T16:20:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。