Large-Scale Frequent Episode Mining from Complex Event Sequences with Hierarchies

doi:10.1145/3326163

	Large-Scale Frequent Episode Mining from Complex Event Sequences with Hierarchies
	Ao, Xiang 1,2; Shi, Haoran 3; Wang, Jin 4; Zuo, Luo 1,2; Li, Hongwei 1,2; He, Qing 1,2
	2019-08-01
发表期刊	ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY
ISSN	2157-6904
卷号	10 期号:4 页码:26
摘要	Frequent Episode Mining (FEM), which aims at mining frequent sub-sequences from a single long event sequence, is one of the essential building blocks for the sequence mining research field. Existing studies about FEM suffer from unsatisfied scalability when faced with complex sequences as it is an NP-complete problem for testing whether an episode occurs in a sequence. In this article, we propose a scalable, distributed framework to support FEM on "big" event sequences. As a rule of thumb, "big" illustrates an event sequence is either very long or with masses of simultaneous events. Meanwhile, the events in this article are arranged in a predefined hierarchy. It derives some abstractive events that can form episodes that may not directly appear in the input sequence. Specifically, we devise an event-centered and hierarchy-aware partitioning strategy to allocate events from different levels of the hierarchy into local processes. We then present an efficient special-purpose algorithm to improve the local mining performance. We also extend our framework to support maximal and closed episode mining in the context of event hierarchy, and to the best of our knowledge, we are the first attempt to define and discover hierarchy-aware maximal and closed episodes. We implement the proposed framework on Apache Spark and conduct experiments on both synthetic and real-world datasets. Experimental results demonstrate the efficiency and scalability of the proposed approach and show that we can find practical patterns when taking event hierarchies into account.
关键词	Frequent episode mining peak episode miner large-scale sequence mining hierarchy-aware maximal/closed episode
DOI	10.1145/3326163
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2017YFB1002104] ; National Natural Science Foundation of China[U1811461] ; National Natural Science Foundation of China[61602438] ; National Natural Science Foundation of China[91846113] ; National Natural Science Foundation of China[61573335] ; CCF-Tencent Rhino-Bird Young Faculty Open Research Fund[RAGR20180111] ; Ant Financial through the Ant Financial Science Funds for Security Research ; Youth Innovation Promotion Association CAS
WOS研究方向	Computer Science
WOS类目	Computer Science, Artificial Intelligence ; Computer Science, Information Systems
WOS记录号	WOS:000496750900004
出版者	ASSOC COMPUTING MACHINERY
引用统计	被引频次：26[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/14789
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wang, Jin
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, 6 Kexueyuan South Rd, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 3.Univ Calif Irvine, Dept Comp Sci, G302 C Student Ctr, Irvine, CA 92697 USA 4.Univ Calif Los Angeles, Comp Sci Dept, 3551 Boelter Hall, Los Angeles, CA 90095 USA
推荐引用方式 GB/T 7714	Ao, Xiang,Shi, Haoran,Wang, Jin,et al. Large-Scale Frequent Episode Mining from Complex Event Sequences with Hierarchies[J]. ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY,2019,10(4):26.
APA	Ao, Xiang,Shi, Haoran,Wang, Jin,Zuo, Luo,Li, Hongwei,&He, Qing.(2019).Large-Scale Frequent Episode Mining from Complex Event Sequences with Hierarchies.ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY,10(4),26.
MLA	Ao, Xiang,et al."Large-Scale Frequent Episode Mining from Complex Event Sequences with Hierarchies".ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY 10.4(2019):26.