提升频繁序列挖掘效率,支持大规模数据快速发现核心事件模式。
Scalable Maximal Frequent Episode Mining with Desbordante
- 重构MaxFEM算法并用C++实现,优化底层计算性能。
- 提出并行化策略,在8核下实现最高35倍加速。
- 集成至Desbordante平台,适合大数据分析与自定义模式挖掘场景。
序列挖掘旨在提取具有特定属性的事件子序列,这些子序列构成对用户有价值的事实。最大频繁序列挖掘关注于发现频繁出现且不被任何更长频繁子序列包含的序列。当前最优方法MaxFEM通过枚举可能子序列并应用多种剪枝技术加速搜索,但该问题计算开销大:降低最小出现次数或增加序列长度都会显著延长运行时间,限制了其实际应用。本文提出改进方案:1)开发高效的C++版本MaxFEM;2)设计有效的并行化技术。由此构建出并行化改进版ParMaxFEM。同时将该算法集成至Desbordante——一个高性能、开源的数据剖析工具,具备深度Python集成能力,将模式视为第一类实体,支持用户编写包含模式发现与验证的自定义程序。实验对比显示,重实现版本相比SPMF基线最高提速8倍,而并行化整体最高达35倍(8核环境)。
原文摘要 · Abstract (English)
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).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。