2019年4月2日上午，来自柏林工业大学数据库系统和信息管理（DIMA, Database Systems and Information Management）小组的研究助理Alexander Renz-Wieland应我院邀请作了题为《Scalable Frequent Sequence Mining with Subsequence Constraints》的报告。报告主要介绍了频繁序列挖掘的算法和应用。
频繁序列挖掘（FSM, Frequent Sequence Mining）是序列数据库中发现频繁子序列的数据挖掘任务。频繁序列挖掘在实际应用中非常广泛，包括：自然语言处理、信息抽取、市场购物篮分析以及计算生物学等。在已有的关于频繁序列挖掘的研究中，很多算法在灵活性和可扩展性方面存在缺陷。图1给出了各种FSM算法的可扩展性和灵活性的分析。
图1. 各种FSM算法的可扩展性和灵活性分析
Alexander Renz-Wieland研究了在灵活子序列的约束下可扩展的频繁序列挖掘算法，推导出了一个用于频繁序列挖掘的一般框架，并在此框架下提出了D-SEQ和D-CAND算法。报告从灵活性和可扩展性两个方面的内容展开。在灵活性方面，使用统一的DESQ框架[ICDM 16]对子序列进行约束，使得应用程序可以用直观、声明式的方式描述灵活的子序列约束，从而减少了对定制的挖掘算法的需求。同时，也提供了一个模式表达式语言来指定子序列约束，该语言的语法类似正则表达式，能够捕获组和层次的结构。在可扩展性方面，他研究了批量同步并行模型与一轮通信，使算法适用于MapReduce或Spark平台。并且通过基于item的分区进行分布式的挖掘。具体框架如图2所示。
图2. 分布式FSM的一般框架
Alexander Renz-Wieland介绍了频繁序列挖掘算法，以及他在算法灵活性和可扩展性方面做出的研究。粗略来说，更灵活的算法旨在支持更广泛的应用程序，可扩展的算法可以处理包含数亿个序列的数据集。期待对这个方向有兴趣的同学深入研究，做出有用的成果。
项目代码：https://github.com/rgemulla/desq/tree/distributed
论文：Renz-Wieland, Bertsch, Gemulla: Scalable Frequent Sequence Mining with Flexible Subsequence Constraints. ICDE ’19.
撰稿：刘婷婷
摄影：王冬慧
排版：方敏
