Efficient algorithms to identify periodic patterns in multiple sequences.

Periodic pattern mining is a popular data mining task, which consists of identifying patterns that periodically appear in data. Traditional periodic pattern mining algorithms are designed to find patterns in a single sequence. However, in several domains, it is desirable to discover patterns that are periodic in many sequences. An example of such application is market basket analysis. Given a database of sequences of transactions made by customers, discovering sets of items that are periodically bought by customers can help understand customer behavior. To discover periodic patterns common to multiple sequences, this paper extends the traditional problem of mining periodic patterns in a sequence. Two novel measures are defined called the standard deviation of periods and the sequence periodic ratio. Two algorithms are proposed to mine these patterns efficiently called MPFPS BFS and MPFPS DFS , which perform a breadth-first search and depth-first search, respectively. Because the sequence periodic ratio is neither monotone nor anti-monotone, these algorithms rely on a novel upper-bound called boundRa and two novel search space pruning properties to find periodic patterns efficiently. The algorithms have been evaluated on multiple datasets. Results show that they are efficient and can filter numerous non periodic itemsets to identify periodic patterns. [ABSTRACT FROM AUTHOR]