Fast, Simple and Memory Efficient Algorithm for Mining Association Rules


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


One of the important problems in data mining is discovering association rules from databases of transactions where each transaction consists of a set of items. The most time consuming operation in this discovery process is the computation of the frequency of the occurrences of interesting subset of items (called candidates) in the database of transactions. In this paper, we introduce algorithms that overcome major drawbacks of previous work. First, for small-scale  database, both the  processing time has been improved significantly. Second, for large-scale database, the proposed algorithms can deal with a database that is substantially larger than the size of available memory. The contributions made in this paper are particularly important because the rate of increase in database size and response time requirements has out-paced advancements in processor and mass storage technology.
Copyright © 2015 Praise Worthy Prize - All rights reserved.

Keywords


Data Mining; Association Rules; Time Consuming; Memory Requirements

Full Text:

PDF


References


R.Agrawal, T. Imielinksi and A. Swami, Database Mining: a performance perspective, IEE Transactions on knowledge and Data Engineering, 1993.

C.-Y. Wang, T.-P. Hong and S.–S. Tseng, Maintenance of discovered sequential patterns for record deletion, Intell. Data Anal, p.p 399-410, February 2002.

Agrawal, T. Imielinski, and A.Sawmi, Mining association rules between sets of items in large databases. In proc. of the ACM SIGMOD Conference on Management of Data,May.1993,p.p 207-216.

R.Agrawal and R.Srikant, Fast algorithms for mining association rules, In Proc. of Intl. Conf. On Very Large Databases (VLDB), Sept. 1994, p.p 487-499.

J. S.Park, M-S. Chen, and P.S.YU, An effective hash based algorithm for mining association rules, In M.J. Carey and D.A. Schneider, editors, Proceedings of the 1995 ACM SIG-MOD International Conference on Management of Data.175-186, San Jose, California, 1995,p.p 22-25.

A.Savasere, E.Omiecinsky, and S.Navathe. An efficient algorithm for mining association rules in large databases. In Proc. 21St International Conference on Very Large Databases (VLDB), Zurich, Switzerland, Also Catch Technical Report No.GIT-CC-95-04, Sept. 1995, p.p 432-443,

Y.F.Jiawei Han, Discovery of multiple-level association rules from large databases, In Proc. of the 21St International Conference on Very Large Databases (VLDB), Zurich, Switzerland, 1995.

D.W-L.Cheung, J.Han, V.Ng, and C.Y.Wong, Maintenance of discovered association rules in large databases : An incremental updating technique, In ICDE, p.p 106-114,1996.

N.F.Ayan, A.U. Tansel, and M.E.Arkm. An efficient algorithm to update large itemsets with early prunning, In Knoweldge discovery and Data Mining. p.p 287-291,1999.

R.Agrawal and R.Srikant, Mining sequential patterns, In P.S.Yu and A.L.P. Chen, editors, Proc.11the Int. Conf. Data engineering, ICDE, p.p 3-14. IEEE, 1995, p.p 6-10.

R.Srikant and R.Agrawal, Mining sequential patterns, Generalizations and performance improvements. Technical report, IBM Alamden Research Center, San Jose, California. 1995.

H.Mannila, H.Toivonen, and A.I.Verkamo. Discovering frequent episodes in sequences. In proceedings of the First International Conference on knowledge Discovery and Data Mining. Pages 210-215, 1995.

H.Mannila, H.Toivonen, and A.I.Verkamo, Discovering frequent episodes in event sequences, Data Mining and knowledge Discovery (1(3) : p.p259-289, 1997).

Y.Huhtala, J.Karkkainen, P.Pokka, and H.Toivonen, TANE : An efficient algorithm for discovering functional and approximate dependencies, The computer Journal, 1999, 42(2): p.p100-111.

Y.Huhtala, J.Kinen, P.Pokka, and H.Toivonen, Efficient discovery of functional and approximate dependencies using partitions, In ICDE,1998, p.p 392-401.

K.Beyer and R.Ramakrishnan, Bottom-up computation of sparse and ice-berg cubes, In Proc. 1999 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’99), Philadelphia, PA, June 1999, p.p 359-370 .

B.Liu, W.Hsu, and Y.Ma, Integrating classification and association rule mining, In Proc. 1998 Int. Conf. Knowledge Discovery and Data Mining (KDD’98), New York, NY, Aug 1998, p.p 80-86.

B.Goethals and M.J.Zaki, Advances in frequent itemset mining implementations : introduction to fimi03, In proceeding of the 1st IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI'03). Nov 2003.

M.S. Chen, J.Han and P.S. Yu, Data Mining: An overview from a database perspective, IEE Transactions on Knowledge and Data Engineering. 1996.

J.Han, J.Pei, and Y.Yin, Mining frequent patterns without candidate generation : A Frequent-Pattern Tree Approach, In Proc. ACM-SIG MOD Int.Conf. Management of Data(SIG MOD'04), 2004, p.p 53-87.

F.Bodon, A Fast apriori implementation, Proc.1st IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI2003, Melbourne, FL), CEURworkshop Pioceedings 90, Aacheme, Germany2003. http:// www. ceur-ws.org/ vol -90/

R. Ivancsy, F.Kovacs and I. Vajk. An analysis of association rule mining algorithms. In CD-ROM proc. Of Fourth International ICSC Symposium on Engineering of Intelligent Systems (EIS), Island of Madeira, Portugal. 2004.

R. Agrawal, C. Aggarwal, and V. V. V. Prasad, A tree pro-jection algorithm for generation of frequent itemsets, In J. of Parallel and Distributed Computing (Special Issue on High Performance Data Mining), 2000.

R. Ivancsy and I. Vajk, Fast Discovery Itemsets: a Cubic Structure-based Approach, Informatica 29, p.p 71-78. 2005.

M. H. Marghny and A.A.Mitwaly, Fast algorithm for mining association rules, In proc. Of the First ICGST International Conference on Artificial Intelligence and Machine Learning AIML05, Dec. 2005, p.p 36-4.

Frequent Itemset Mining Implementations (FIMI’04) WorkShop website, http:// fimi. cs. helsinki.fi, 2004.


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2023 Praise Worthy Prize