More Web Proxy on the site http://driver.im/

Article

Efficient closed pattern mining in the presence of tough block constraints

Authors:

George KarypisAuthors Info & Claims

KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 138 - 147

https://doi.org/10.1145/1014052.1014070

Published: 22 August 2004 Publication History

Abstract

Various constrained frequent pattern mining problem formulations and associated algorithms have been developed that enable the user to specify various itemset-based constraints that better capture the underlying application requirements and characteristics. In this paper we introduce a new class of block constraints that determine the significance of an itemset pattern by considering the dense block that is formed by the pattern's items and its associated set of transactions. Block constraints provide a natural framework by which a number of important problems can be specified and make it possible to solve numerous problems on binary and real-valued datasets. However, developing computationally efficient algorithms to find these block constraints poses a number of challenges as unlike the different itemset-based constraints studied earlier, these block constraints are tough as they are neither anti-monotone, monotone, nor convertible. To overcome this problem, we introduce a new class of pruning methods that significantly reduce the overall search space and present a computationally efficient and scalable algorithm called CBMiner to find the closed itemsets that satisfy the block constraints.

References

[1]

R. Agarwal, C. Aggarwal, V. Prasad, and V. Crestana. A tree projection algorithm for generation of large itemsets for association rules. IBM Research Report, RC21341, November 1998.]]

[2]

R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. of the VLDB'94, September 1994.]]

Digital Library

[3]

R. Bayardo. Efficiently mining long patterns from databases. In Proc. of the ACM SIGMOD'98, June 1998.]]

Digital Library

[4]

R. Bayardo, R. Agrawal, and D. Gunopulos. Constrained based rule mining for large dense databases. In Proc. of the ICDE'99, March 1999.]]

Digital Library

[5]

S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In Proc. of the ACM SIGMOD'97, May 1997.]]

Digital Library

[6]

C. Bucila, J. Gehrke, D. Kifer, and W. White. Dualminer : A dual-pruning algorithm for itemsets with constraints. In Proc. of the ACM SIGKDD'02, July 2002.]]

Digital Library

[7]

D. Burdick, M. Calimlim, and J. Gehrke. Mafia: A maximal frequent itemset algorithm for transactional databases. In Proc. of the ICDE'01, April 2001.]]

Digital Library

[8]

A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd Edition. Adison Wesley Publishing Company, 2003.]]

[9]

J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. In Proc. of the ACM SIGMOD'00, May 2000.]]

Digital Library

[10]

K. Gade, J. Wang, and G. Karypis. Effcient Closed Pattern Mining in the Presence of Tough Block Constraints. Technical Report TR #03--45, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 2003. Available on the WWW at: http://cs.umn.edu/~karypis/publications.]]

[11]

G. Karypis and E. H. Han. Fast supervised dimensionality reduction algorithm with applications to document categorization & retrieval. In Proc. of the ACM CIKM'00, November 2000.]]

Digital Library

[12]

D. Kifer, C. Bucila, J. Gehrke, and W. White. How to quickly find a witness. In Proc. of the ACM PODS'03, June 2003.]]

Digital Library

[13]

C.K.-S. Leung, L.V.S. Lakshmanan, and R.T. Ng. Exploiting succinct constraitnts using fp-trees. In ACM SIGKDD Explorations, Volume 4, 2002.]]

Digital Library

[14]

B. Liu, W. Hsu, and Y. Ma. Mining association rules with multiple minimum supports. In Proc. of the ACM SIGKDD'99, August 1999.]]

Digital Library

[15]

G. Liu, H. Lu, W. Lou, and J.X. Yu. On computing and querying frequent patterns. In Proc. of the ACM SIGKDD'03, August 2003.]]

Digital Library

[16]

R. Ng, Laks V. S. Lakshmanan, J. Han, and T. Mah. Exploratory mining via constrained frequent set queries. In Proc. of the ACM SIGMOD'99, June 1999.]]

Digital Library

[17]

N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Discovering frequent closed itemsets for association rules. In Proc. of the ICDT'99, January 1999.]]

Digital Library

[18]

J. Pei and J. Han. Constrained frequent pattern mining : A pattern-growth view. In ACM SIGKDD Explorations, Volume 4, 2002.]]

Digital Library

[19]

J. Pei, J. Han, and L.V.S. Lakshmanan. Mining frequent itemsets with convertible constraints. In Proc. of the ICDE'01, April 2001.]]

Digital Library

[20]

J. Pei, J. Han, H. Liu, and S. Nishio et al. H-mine : Hyper structure mining of frequent patterns databases. In Proc. of the ICDM'01, November 2001.]]

Digital Library

[21]

J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In Proc. of the DMKD'00, May 2000.]]

[22]

M. Seno and G. Karypis. Lpminer: An algorithm for finding frequent itemsets using length-decreasing support constraint. In Proc. of the ICDM'01, November 2001.]]

Digital Library

[23]

R. Srikant, Q. Vu, and R. Agrawal. Mining associations rules with item constraints. In Proc. of the ACM SIGKDD'97, August 1997.]]

[24]

J. Wang, J. Han, and J. Pei. Closet+: Searching for the best strategies for mining frequent closed itemsets. In Proc. of the ACM SIGKDD'03, August 2003.]]

Digital Library

[25]

K. Wang, Y. He, and J. Han. Mining frequent itemsets using support constraints. In Proc. of the VLDB'00, September 2000.]]

Digital Library

[26]

K. Wang, Y. Jiang, J. Xu Yu, G. Dong, and J. Han. Pusing aggregate constraints by divide-and-approximate. In Proc. of the ICDE'03, March 2003.]]

[27]

J. Wang and G. Karypis. BAMBOO: Accelerating closed itemset mining by deeply pushing the length-decreasing support constraint. In Proc. of the SDM'04, April 2004.]]

[28]

M. Zaki. Generating non-redundant association rules. In Proc. of the ACM SIGKDD'00, August 2000.]]

Digital Library

[29]

M. Zaki and C. Hsiao. Charm: An efficient algorithm for closed itemset mining. In Proc. of the SDM'02, April 2002.]]

Cited By

Pazhaniraja NBasheer SThirugnanasambandam KRamalingam RRashid MKalaivani J(2023)Multi-objective Boolean grey wolf optimization based decomposition algorithm for high-frequency and high-utility itemset miningAIMS Mathematics10.3934/math.20239208:8(18111-18140)Online publication date: 2023
https://doi.org/10.3934/math.2023920
Rahman MArefin MRahman SAhmed AIslam TDhar PKwon O(2022)A Comprehensive Survey on Affinity Analysis, Bibliomining, and Technology Mining: Past, Present, and Future ResearchApplied Sciences10.3390/app1210522712:10(5227)Online publication date: 21-May-2022
https://doi.org/10.3390/app12105227
Kumar RSingh K(2022)A survey on soft computing-based high-utility itemsets miningSoft Computing10.1007/s00500-021-06613-426:13(6347-6392)Online publication date: 25-Jan-2022
https://doi.org/10.1007/s00500-021-06613-4
Show More Cited By

Index Terms

Efficient closed pattern mining in the presence of tough block constraints
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Closed frequent similar pattern mining

The concept of closed frequent similar pattern mining is introduced.Several lemmas to prune the search space are introduced and proved.A novel closed frequent similar pattern mining algorithm (CFSP-Miner), is proposed.CFSP-Miner is more efficient than ...
TSP: Mining top-k closed sequential patterns

Sequential pattern mining has been studied extensively in the data mining community. Most previous studies require the specification of a min_support threshold for mining a complete set of sequential patterns satisfying the threshold. However, in ...
Tough constraint-based frequent closed itemsets mining
SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

Mining frequent itemsets has been one of the hot topics in data mining. Candidate generation-and-test approaches such as Apriori have been proved to be effective. However, in practical applications, we will face a lot of intractable frequent itemsets ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

August 2004

874 pages

ISBN:1581138881

DOI:10.1145/1014052

General Chairs:
Won Kim
Cyber Database Solutions
,
Ronny Kohavi
Amazon.com
,
Program Chairs:
Johannes Gehrke
Cornell University
,
William DuMouchel
AT&T Labs Research

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD04

Sponsor:

KDD04: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 22 - 25, 2004

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
754
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pazhaniraja NBasheer SThirugnanasambandam KRamalingam RRashid MKalaivani J(2023)Multi-objective Boolean grey wolf optimization based decomposition algorithm for high-frequency and high-utility itemset miningAIMS Mathematics10.3934/math.20239208:8(18111-18140)Online publication date: 2023
https://doi.org/10.3934/math.2023920
Rahman MArefin MRahman SAhmed AIslam TDhar PKwon O(2022)A Comprehensive Survey on Affinity Analysis, Bibliomining, and Technology Mining: Past, Present, and Future ResearchApplied Sciences10.3390/app1210522712:10(5227)Online publication date: 21-May-2022
https://doi.org/10.3390/app12105227
Kumar RSingh K(2022)A survey on soft computing-based high-utility itemsets miningSoft Computing10.1007/s00500-021-06613-426:13(6347-6392)Online publication date: 25-Jan-2022
https://doi.org/10.1007/s00500-021-06613-4
Wang TDesai BDesai BAnagnostopoulos DManolopoulos YNikolaidou M(2019)On the appropriate pattern frequentness measure and pattern generation modeProceedings of the 23rd International Database Applications & Engineering Symposium10.1145/3331076.3331125(1-15)Online publication date: 10-Jun-2019
https://dl.acm.org/doi/10.1145/3331076.3331125
Cao HYang SWang QWang QZhang L(2019)A Closed Itemset Property based Multi-objective Evolutionary Approach for Mining Frequent and High Utility Itemsets2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8789985(3356-3363)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8789985
Leung C(2018)Frequent Itemset Mining with ConstraintsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_170(1531-1536)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_170
Leung C(2017)Frequent Itemset Mining with ConstraintsEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_170-2(1-6)Online publication date: 9-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_170-2
Zhang LLuo PTang LChen ELiu QWang MXiong H(2015)Occupancy-Based Frequent Pattern Mining*ACM Transactions on Knowledge Discovery from Data10.1145/275376510:2(1-33)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2753765
Tang LZhang LLuo PWang MChen XLebanon GWang HZaki M(2012)Incorporating occupancy into frequent pattern mining for high quality pattern recommendationProceedings of the 21st ACM international conference on Information and knowledge management10.1145/2396761.2396775(75-84)Online publication date: 29-Oct-2012
https://dl.acm.org/doi/10.1145/2396761.2396775
Zhang LTang LLuo PChen EJiao LWang MLiu GYang QAgarwal DPei J(2012)Harnessing the wisdom of the crowds for accurate web page clippingProceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2339530.2339621(570-578)Online publication date: 12-Aug-2012
https://dl.acm.org/doi/10.1145/2339530.2339621
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents