High Utility Episode Mining Made Practical and Fast

Publication Type

Conference Proceeding Article

Publication Date

12-2014

Abstract

This paper focuses on the problem of mining high utility episodes from complex event sequences. Episode mining, one of the fundamental problems of sequential pattern mining, has been continuously drawing attention over the past decade. Meanwhile, there is also tremendous interest in the problem of high utility mining. Recently, the problem of high utility episode mining comes into view from the interface of these two research areas. Although prior work [11] has proposed algorithm UP-Span to tackle this problem, their method suffers from several performance drawbacks. To that end, firstly, we explicitly interpret the high utility episode mining problem as a complete traversal of the lexicographic prefix tree. Secondly, under the framework of lexicographic prefix tree, we examine the original UP-Span algorithm and present several improvements on it. In addition, we propose several clever strategies from a practical perspective and obtain much tighter utility upper bounds of a given node. Based on these optimizations, an efficient algorithm named TSpan is presented for fast high utility episode mining using tighter upper bounds, which reduces huge search space over the prefix tree. Extensive experiments on both synthetic and real-life datasets demonstrate that TSpan outperforms the state-of-the-art in terms of both search space and running time significantly.

Discipline

Databases and Information Systems

Publication

Advanced Data Mining and Applications: 10th International Conference, ADMA 2014, Guilin, China, December 19-21, 2014: Proceedings

Volume

8933

First Page

71

Last Page

84

ISBN

9783319147161

Identifier

10.1007/978-3-319-14717-8_6

Publisher

Springer Verlag

City or Country

Cham

Additional URL

http://dx.doi.org/10.1007/978-3-319-14717-8_6

Link to Full Text

Share

COinS