A High-Performance Algorithm for Mining Repeating Patterns

摘要

A repeating pattern is a sequence composed of identical elements, repeating in a regular manner. In real life, there are lots of applications such as musical and medical sequences containing valuable repeating patterns. Because the repeating patterns hidden in sequences might contain implicit knowledge, how to retrieve the repeating patterns effectively and efficiently has been a challenging issue in recent years. Although a number of past studies were proposed to deal with this issue, the performance cannot still earn users' satisfactions especially for large datasets. To aim at this issue, in this paper, we propose an efficient algorithm named Fast Mining of Repeating Patterns (FMRP), which achieves high performance for finding repeating patterns by a novel index called Quick-Pattern-Index (QPI). This index can provide the proposed FMRP algorithm with an effective support due to its information of pattern positions. Without scanning a given sequence iteratively, the repeating patterns can be discovered by only one scan of the sequence. The experimental results reveal that our proposed algorithm performs better than the compared methods in terms of execution time.