Fast vertical mining using diffsets

ABSTRACT

A number of vertical mining algorithms have been proposed recently for association mining, which have shown to be very effective and usually outperform horizontal approaches. The main advantage of the vertical format is support for fast frequency counting via intersection operations on transaction ids (tids) and automatic pruning of irrelevant data. The main problem with these approaches is when intermediate results of vertical tid lists become too large for memory, thus affecting the algorithm scalability.In this paper we present a novel vertical data representation called Diffset, that only keeps track of differences in the tids of a candidate pattern from its generating frequent patterns. We show that diffsets drastically cut down the size of memory required to store intermediate results. We show how diffsets, when incorporated into previous vertical mining methods, increase the performance significantly.

REFERENCES

• 1: 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
• 2: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, Depth first generation of long patterns, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.108-118, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347114]
• 3: Jay Ayres , Jason Flannick , Johannes Gehrke , Tomi Yiu, Sequential PAttern mining using a bitmap representation, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775109]
• 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: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 6: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 7: Data Organization and Access for Efficient Data Mining, Proceedings of the 15th International Conference on Data Engineering, p.522, March 23-26, 1999
• 8: Karam Gouda , Mohammed Javeed Zaki, Efficiently Mining Maximal Frequent Itemsets, Proceedings of the 2001 IEEE International Conference on Data Mining, p.163-170, November 29-December 02, 2001
• 9: Dimitrios Gunopulos , Heikki Mannila , Sanjeev Saluja, Discovering All Most Specific Sentences by Randomized Algorithms, Proceedings of the 6th International Conference on Database Theory, p.215-229, January 08-10, 1997
• 10: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 11: 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
• 12: Dao-I Lin , Zvi M. Kedem, Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.105-119, March 23-27, 1998
• 13: Jun-Lin Lin , Margaret H. Dunham, Mining Association Rules: Anti-Skew Algorithms, Proceedings of the Fourteenth International Conference on Data Engineering, p.486-493, February 23-27, 1998
• 14: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 15: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 16: J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In SIGMOD Int'l Workshop on Data Mining and Knowledge Discovery, May 2000.
• 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: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 19: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 20: Pradeep Shenoy , Jayant R. Haritsa , S. Sundarshan , Gaurav Bhalotia , Mayank Bawa , Devavrat Shah, Turbo-charging vertical mining of large databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.22-33, May 15-18, 2000, Dallas, Texas, United States
• 21: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]
• 22: Mohammed J. Zaki, Scalable Algorithms for Association Mining, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.372-390, May 2000 [doi>10.1109/69.846291 ]
• 23: M. J. Zaki and C.-J. Hsiao. CHARM: An efficient algorithm for closed itemset mining. In 2nd SIAM Int'l Conf. on Data Mining, April 2002.
• 24: M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In 3rd Intl. Conf. on Knowledge Discovery and Data Mining, August 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
association rule mining, diffsets, frequent itemsets