On Mining Repeating Pattern with Gap Constraint

Abstract

We in this paper propose a new concept, repeating patterns with gap constraint, to make repeating patterns tolerate the delay of events. To mine repeating patterns with gap constraint, we first show the anti-monotonic property of repeating patterns with gap constraint and then propose a level-wise algorithm, named G-Apriori (standing for Gap with Apriori), based on the anti-monotonic property. Similar to other level-wise mining algorithms such as Apriori, algorithm G-Apriori will scan databases several times to count the number of occurrences of each candidate repeating pattern. Such phenomenon makes G-Apriori spend much time in disk I/O, thereby making G-Apriori not suitable for large databases. In view of this, we develop an index structure to record the positions of the occurrences of each repeating pattern, and then propose algorithm GwI-Apriori (standing for Gap with Index Apriori) to utilize the index structure to reduce the number of database scans when mining repeating patterns with gap constraint. The experimental results show that algorithm GwI-Apriori is more scalable than algorithm G-Apriori in terms of execution time.