Sliding-window filtering: an efficient algorithm for incremental mining

ABSTRACT

We explore in this paper an effective sliding-window filtering (abbreviatedly as SWF) algorithm for incremental mining of association rules. In essence, by partitioning a transaction database into several partitions, algorithm SWF employs a filtering threshold in each partition to deal with the candidate itemset generation. Under SWF, the cumulative information of mining previous partitions is selectively carried over toward the generation of candidate itemsets for the subsequent partitions. Algorithm SWF not only significantly reduces I/O and CPU cost by the concepts of cumulative filtering and scan reduction techniques but also effectively controls memory utilization by the technique of sliding-window partition. Algorithm SWF is particularly powerful for efficient incremental mining for an ongoing time-variant transaction database. By utilizing proper scan reduction techniques, only one scan of the incremented dataset is needed by algorithm SWF. The I/O cost of SWF is, in orders of magnitude, smaller than those required by prior methods, thus resolving the performance bottleneck. Experimental studies are performed to evaluate performance of algorithm SWF. It is noted that the improvement achieved by algorithm SWF is even more prominent as the incremented portion of the dataset increases and also as the size of the database increases.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 2: 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
• 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: Necip Fazil Ayan , Abdullah Uz Tansel , Erol Arkun, An efficient algorithm to update large itemsets with early pruning, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.287-291, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312252]
• 5: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, ACM SIGMOD Record, v.26 n.2, p.255-264, June 1997
• 6: Ming-Syan Chen , Jiawei Han , Philip S. Yu, Data Mining: An Overview from a Database Perspective, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.866-883, December 1996 [doi>10.1109/69.553155]
• 7: Ming-Syan Chen , Jong Soo Park , Philip S. Yu, Efficient Data Mining for Path Traversal Patterns, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.209-221, March 1998 [doi>10.1109/69.683753]
• 8: David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996
• 9: David Wai-Lok Cheung , Sau Dan Lee , Ben Kao, A General Incremental Technique for Maintaining Discovered Association Rules, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.185-194, April 01-04, 1997
• 10: Jiawei Han , Laks V. S. Lakshmanan , Raymond T. Ng, Constraint-Based, Multidimensional Data Mining, Computer, v.32 n.8, p.46-50, August 1999 [doi>10.1109/2.781634]
• 11: Jiawei Han , Jian Pei, Mining frequent patterns by pattern-growth: methodology and implications, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.14-20, Dec. 2000 [doi>10.1145/380995.381002]
• 12: Jiawei Han , Jian Pei , Behzad Mortazavi-Asl , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.355-359, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347167]
• 13: Jochen Hipp , Ulrich Güntzer , Gholamreza Nakhaeizadeh, Algorithms for association rule mining — a general survey and comparison, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.58-64, June, 2000 [doi>10.1145/360402.360421]
• 14: 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
• 15: 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
• 16: 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]
• 17: Jian Pei , Jiawei Han, Can we push more constraints into frequent pattern mining?, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.350-354, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347166]
• 18: 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
• 19: 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
• 20: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 21: S. Thomas, S. Bodagala, K. Alsabti, and S. Ranka. An Efficient Algorithm for the Incremental Updation of Association Rules in Large Databases. Proc. of 1997 Ink Conf. on Knowledge Discovery and Data Mining, 1997.
• 22: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 23: Anthony K. H. Tung , Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han, Constraint-based clustering in large databases, Proceedings of the 8th International Conference on Database Theory, p.405-419, January 04-06, 2001
• 24: Ke Wang , Yu He , Jiawei Han, Mining Frequent Itemsets Using Support Constraints, Proceedings of the 26th International Conference on Very Large Data Bases, p.43-52, September 10-14, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Performance

Keywords:
association rules, data mining, incremental mining, time-variant database