A Sliding Window Approach to Mine Negative and Positive Regular Patterns in Incremental Databases Using Vertical Data Format


  • N V.S. Pavan Kumar
  • K Rajasekhara Rao




Incremental Mining, Negative Association Rules, Negative Patterns, Regular Patterns


Incremental databases are the repositories of most emerging realistic data from ecommerce sites and other sources. They are typical in nature as new transactions are added to the database along with the progression in time. Regular patterns are more advanced and reliable as they describe not only occurrence frequency but also occurrence behavior. Finding negatively associated positive patterns is very complex process because of  search space and the size of the database. These not overlapping patterns play a vital role in decision making by extracting complex hidden knowledge from the transactional databases. Sliding window progresses with time leaving the old transactions from one end and keep on including new transactions from other end. Vertical format of database is very much handy in finding regular itemset. There was no much effort made earlier by the researchers in this area of KDD. Hence we have developed an algorithm INC_Nprism to find all the negative and positive regular itemset from incremental databases using vertical format with a sliding window. Unlike some earlier algorithms we need not construct any tree structure with this approach. Also multiple scans of database are also not required with this approach. Experimental results proved that our algorithm works efficiently and yields most satisfying results.




[1] Agarwal, R., Imielinski, T., Swamy, A.N.: Mining Association Rules between sets of Items in Large Databases, ACM, SIGMOD Conference of Management of Data, pp. 207-216 (1993).

[2] Farhan Ahmed, Tanbeer, Byeong-Soo Jeong “ A frame work for mining high utility web access sequence “ IETE Technical Review 28(1) · January 2011

[3] Agarwal, R., Srikanth, R. Fast algorithms for mining association rules, In Proc. 1994 International Conference on very large databases (VLDBA’94), Santiago, Chile, pp. 487-499, Sept. 1994.

[4] Elfeky, M.G., Aref, W.G., Elmagarmid, A.K. Periodicity detection in time series databases, IEEE Transactions on Knowledge and Data Engineering 17(7), pp. 875-887 (2005).

[5] Han, J., Pei, J., Yin, Y. Mining frequent patterns without candidate generation, In Proc. ACM, SIGMOD, International Conference on Management of Data, 2000, pp. 1-12.

[6] N V S Pavan Kumar, K Rajasekhara Rao “Mining Positive and Negative Regular Item-Sets using Vertical Databases†IJSSST.a.17.32.33, pp. 232-248, 2016.

[7] Xie Zhi-jun Chen Hong Cuiping Li An Efficient Algorithm for Frequent Itemset Mining on Data Streams ICDM 2006: Advances in Data Mining. Applications in Medicine, Web Mining, Marketing, Image and Signal Mining pp 474-491

[8] Diana Martín, Alejandro Rosete , Jess Alcalá-Fdez , Francisco Herrera, “A New Multiobjective Evolutionary Algorithm for Mining a Reduced Set of Interesting Positive and Negative Quantitative Association Rules†EEE Transactions on Evolutionary Computation , Volume: 18, Issue: 1, Feb. 2014

[9] Yue-ShiLeeShow-JaneYen “Incremental and interactive mining of web traversal patterns†Information Sciences Volume 178, Issue 2, 15 January 2008, Pages 287-306

[10] Chowdhury Farhan Ahmed, Syed Khairuzzaman Tanbeer, Byeong-Soo Jeong, and Young-koo Lee “Efficient mining of Utility-Based web path Traversal Patternsâ€, ISBN 978-89-5519-139-4,Feb.15-18,2009 ICACT 2009.

[11] L. Zhou, Y. Liu, J. Wang, and Y. Shi. "Utility-based Web Path Traversal Pattern Mining", in: Proceedings of the 7th IEEE International conference on Data Mining Workshops, pp. 373-8, 2007.

[12] LeiChang, TengjiaoWang, DongqingYang, HuaLuanc,, ShiweiTangad, “Efficient algorithms for incremental maintenance of closed sequential patterns in large databases†,Data & Knowledge Engineering Volume 68, Issue 1, January 2009, Pages 68-106.

[13] Jigyasa Bisaria, Namita Shrivastava, K.R. Pardasan “A Rough Sets Partitioning Model for Mining Sequential Patterns with Time Constraintâ€, (IJCSIS) International Journal of Computer Science and Information Security, Vol. 2, No. 1, 2009

[14] Chun-Jung, ChuaVincent, S.Tsengb, TyneLianga, “An efficient algorithm for mining high utility itemsets with negative item values in large databases Applied Mathematics and Computationâ€, Volume 215, Issue 2, 15 September 2009, Pages 767-778

[15] Eya Ben Ahmed, Ahlem Nabli and Fäıez Gargouri “Cyclic Association Rules:Coupling Multiple Levels and Parallel Dimension Hierarchiesâ€, Proceedings of the International Conference on Information and Knowledge Engineering (IKE); Athens 2011.

[16] Zaki, M.J., Karam, G. “Fast Vertical Mining using Diffsetsâ€, SIGKDD’03, August 24-27, 2003, Copyright 2003 ACM 1-58113-737-0/03/0008.

[17] Tanbeer, S.K., Ahmed, C.F., Jeong, B.S. Lee, Y-K, “Mining Regular Patterns in Incremental Transactional Databases, 12th International Asia-Pacific web conference, 2010 IEEE, DOI 10.1109/APWeb.2010.68, pp.375-377.

[18] Yi-ming, G., Zhi-jun, W. A Vertical format algorithm for mining frequent itemsets, IEEE Transactions, pp. 11-13, 2010.

[19] Ahmed, C. F., Tanbeer, S. K., Jeong, B. S., & Lee, Y. K. “An efficient algorithm for sliding window-based weighted frequent pattern mining over data streamsâ€.IEICE Transactions, Vol. 92-D(7),pp. 1369–1381, 2009.

[20] Chih-Hsiang Lin, Ding-Ying Chiu, Yi-Hung Wu, Arbee L. P. Chen, “Mining Frequent Itemsets from Data Streams with a Time-Sensitive Sliding Windowâ€, in Society for industrial and applied mathematics, 2005.

[21] Vijay Kumar, G., Sreedevi, M., Pavan Kumar NVS. Mining Regular Patterns in Transactional Databases using vertical Format, IJARCS, Sep-Oct 2011, pp. 581-583.

[22] Vijay Kumar, G., Sreedevi, M., Pavan Kumar NVS A Vertical Format to Mine Regular Patterns in Incremental Transactional Databasesâ€, Journal Of Computing, Volume 3, Issue 11, November 2011, ISSN 2151-9617

[23] Vijay Kumar, G., Valli Kumari, V., “Incremental Mining for Regular Frequent Patterns in Vertical Format†International Journal of Engineering and Technology, Vol 5 No 2, 2013.

[24] Vijay Kumar, G., Valli Kumari, V., “Sliding Window Technique to Mine Regular Frequent Patterns in Data Streams using Vertical Formatâ€, 2012 IEEE International Conference on Computational Intelligence and Computing Research, 2012.

[25] C. Cornells, Y. Peng, Z. Xing, and C. Guoqing, "Mining Positive and Negative Association Rules from Large Databases," in IEEE Conference on Cybernetics and Intelligent Systems, 2006, pp. 1-6.

[26] W. Xindong, Z. Chengqi, and Z. Shichao, "Efficient mining of both positive and negative association rules," ACM Transactions on Information Systems (TOIS), vol. 22, pp. 381-405, 2004.

View Full Article: