Scalable Maximal Frequent Episode Mining with Desbordante
2026-07-03 • Databases
DatabasesArtificial IntelligenceDistributed, Parallel, and Cluster ComputingMachine LearningPerformance
AI summaryⓘ
The authors worked on improving an algorithm called MaxFEM that finds frequently repeating sequences of events, which is useful but usually very slow when sequences get longer or appear less often. They rewrote MaxFEM in faster C++ code and created a way to run it on multiple processor cores at the same time. This new version, called ParMaxFEM, runs much faster—up to 35 times quicker with parallelization—compared to the original. They also included it in an open-source tool named Desbordante, making it easier for users to find and use these event patterns in their own programs.
Episode miningMaximal frequent episode miningMaxFEM algorithmSubsequencePruning techniquesParallel computingC++ implementationPerformance optimizationSPMFDesbordante
Authors
Maxim Ivanov, Matvei Smirnov, Alisa Strazdina, George Chernishev
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).