TY - GEN
T1 - On mining repeating pattern with gap constraint
AU - Chiu, Shin Yi
AU - Chiu, Shih Chuan
AU - Huang, Jiun-Long
PY - 2009/11/20
Y1 - 2009/11/20
N2 - 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 GwIApriori (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.
AB - 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 GwIApriori (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.
UR - http://www.scopus.com/inward/record.url?scp=70449568263&partnerID=8YFLogxK
U2 - 10.1109/HPCC.2009.65
DO - 10.1109/HPCC.2009.65
M3 - Conference contribution
AN - SCOPUS:70449568263
SN - 9780769537382
T3 - 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009
SP - 557
EP - 562
BT - 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009
Y2 - 25 June 2009 through 27 June 2009
ER -