On mining repeating pattern with gap constraint

Shin Yi Chiu*, Shih Chuan Chiu, Jiun-Long Huang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 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.

Original languageEnglish
Title of host publication2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009
Pages557-562
Number of pages6
DOIs
StatePublished - 20 Nov 2009
Event11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009 - Seoul, Korea, Republic of
Duration: 25 Jun 200927 Jun 2009

Publication series

Name2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009

Conference

Conference11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009
CountryKorea, Republic of
CitySeoul
Period25/06/0927/06/09

Cite this

Chiu, S. Y., Chiu, S. C., & Huang, J-L. (2009). On mining repeating pattern with gap constraint. In 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009 (pp. 557-562). [5167044] (2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009). https://doi.org/10.1109/HPCC.2009.65