A new algorithm for gap constrained sequence mining

The sequence mining problem consists in nding frequent sequential patterns in a database of time-stamped events. Several application domains require limiting the maximum temporal gap between events occurring in the input sequences. However pushing down such constraint is critical for most sequence mining algorithms. In this paper we describe CCSM (Cache-based Constrained Sequence Miner), a new level-wise algorithm that overcomes the troubles usually related to this kind of constraints. CCSM adopts an innovative approach based on kway intersections of idlists to compute the support of candidate sequences. Our k-way intersection method is enhanced by the use of an effective cache that stores intermediate idlists for future reuse. The reuse of intermediate results entails a surprising reduction in the actual number of join operations performed on idlists. CCSM has been experimentally compared with cSPADE, a state of the art algorithm, on several synthetically generated datasets, obtaining better or similar results in most cases.