Exploiting succinct constraints using FP-trees

ABSTRACT

Since its introduction, frequent-set mining has been generalized to many forms, which include constrained data mining. The use of constraints permits user focus and guidance, enables user exploration and control, and leads to effective pruning of the search space and efficient mining of frequent itemsets. In this paper, we focus on the use of succinct constraints. In particular, we propose a novel algorithm called FPS to mine frequent itemsets satisfying succinct constraints. The FPS algorithm avoids the generate-and-test paradigm by exploiting succinctness properties of the constraints in a FP-tree based framework. In terms of functionality, our algorithm is capable of handling not just the succinct aggregate constraint, but any succinct constraint in general. Moreover, it handles multiple succinct constraints. In terms of performance, our algorithm is more efficient and effective than existing FP-tree based constrained frequent-set mining algorithms.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Hiekki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: Constraint-Based Rule Mining in Large, Dense Databases, Proceedings of the 15th International Conference on Data Engineering, p.188, March 23-26, 1999
• 6: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 7: Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.13-23, June 04-06, 1996, Montreal, Quebec, Canada
• 8: Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, SPIRIT: Sequential Pattern Mining with Regular Expression Constraints, Proceedings of the 25th International Conference on Very Large Data Bases, p.223-234, September 07-10, 1999
• 9: Efficient Mining of Constrained Correlated Sets, Proceedings of the 16th International Conference on Data Engineering, p.512, February 28-March 03, 2000
• 10: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 11: Laks V. S. Lakshmanan , Raymond Ng , Jiawei Han , Alex Pang, Optimization of constrained frequent set queries with 2-variable constraints, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.157-168, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: L. V. S. Lakshmanan and R. T. Ng. A theory of succinctness and its application to constrained analysis and mining. In preparation, 2002.
• 13: R. J. Miller , Y. Yang, Association rules over interval data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.452-461, May 11-15, 1997, Tucson, Arizona, United States
• 14: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 15: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.813-825, September 1997 [doi>10.1109/69.634757]
• 16: Jian Pei , Jiawei Han , Laks V. S. Lakshmanan, Mining Frequent Item Sets with Convertible Constraints, Proceedings of the 17th International Conference on Data Engineering, p.433-442, April 02-06, 2001
• 17: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 18: Craig Silverstein , Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman, Scalable Techniques for Mining Causal Structures, Proceedings of the 24rd International Conference on Very Large Data Bases, p.594-605, August 24-27, 1998
• 19: R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. In Proc. KDD 1997, pp. 67-73.
• 20: Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.1-12, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory

Keywords:
FP-trees, constraints, data mining, frequent sets, succinctness