Algorithms And Data Structures For Association Rule Mining And Its Complexity Analysis

Algorithms are characterized by the time of solution of the problem and the data structure used.We propose a method for estimating the time complexity and space complexity and analyze algorithms for association rules mining. To compare the algorithms, we estimate the time complexity of each iteration of processing of all transactions in the worst case. The space complexity is estimated from the size of data structure used by the algorithm, without taking into account its physical implementation in the development of software. The worst case is also used. In accordance with the method, we estimate the time and space complexities of following algorithms: the Apriori algorithm, the FP-Growth algorithm, the matrix algorithm, the SimpleARM algorithm, the algorithm using multi-layer matrix quadrants, and algorithms using the transposition of transaction table. These algorithms use various types of the data structure such as: matrices, trees, and lists. Analyzed result of estimating we conclude that no algorithm surpasses the others by compared complexity. We also survey problems related to association rule mining: sequential pattern mining and association rule hiding