Towards efficient mining of non-redundant recurrent rules from a sequence database
Seungyong Yoon, Hirohisa Seki · 2017
There have been studied many methods for mining sequential patterns from a sequence database. Lo et al. have proposed the notion of recurrent rules and an algorithm called NR3for mining them. Since recurrent rules are able to describe temporal constraints such as “Whenever a series of precedent events occurs, eventually a series of consequent events occurs,” they are shown to useful in various domains, including software specification and verification. Although the algorithm NR3and its successor BOB for mining non-redundant recurrent rules have been proposed by Lo et al., mining recurrent rules still requires considerable computational costs. In this paper, we propose a new algorithm, called LF-NR3, to make NR3more efficient; our approach is based on the application of loop fusion, a familiar program transformation, to NR3, thereby removing some overheads existing in the original mining algorithm. We also make use of a hash-based data structure to make efficient the manipulation of sequences repeatedly required in mining recurrent rules. We present some experimental results, which show the effectiveness of our proposed method.