Tight upper bounds on the number of candidate patterns
ACM Transactions on Database SystemsPublished 1 June 2005
Floris Geerts, Bart Goethals, Jan Van den Bussche
Citations30
SJR quartileQ1
SJR score0.91
SNIP1.85
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
In the context of mining for frequent patterns using the standard levelwise algorithm, the following question arises: given the current level and the current set of frequent patterns, what is the maximal number of candidate patterns that can be generated on the next level? We answer this question by providing tight upper bounds, derived from a combinatorial result from the sixties by Kruskal and Katona. Our result is useful to secure existing algorithms from a combinatorial explosion of the number of candidate patterns.
Keywords
Computer Science
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +1 more
Mining frequent patterns without candidate generation
3,195 Citations2000Jiawei Han, Jian Pei +1 more
This study proposes a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develops an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth.
Dynamic itemset counting and implication rules for market basket data
1,954 Citations1997Sergey Brin, Rajeev Motwani +2 more
A new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling and a new way of generating “implication rules” which are normalized based on both the antecedent and the consequent.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
An effective hash-based algorithm for mining association rules
1,412 Citations1995Jong Soo Park, Ming-Syan Chen⋆ +1 more
The number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck, and allows us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly.
Lecture notes in computer scienceDiscovering Frequent Closed Itemsets for Association Rules
1,361 Citations1999Nicolas Pasquier, Yves Bastide +2 more
This paper proposes a new algorithm, called A-Close, using a closure mechanism to find frequent closed itemsets, and shows that this approach is very valuable for dense and/or correlated data that represent an important part of existing databases.
Efficiently mining long patterns from databases
1,297 Citations1998Roberto J. Bayardo
A pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern, compared with previous algorithms that scale exponentially with longest pattern length.
New algorithms for fast discovery of association rules
1,112 Citations1997Mohammed J. Zaki, Srinivasan Parthasarathy +2 more
New algorithms for fast association mining, which scan the database only once, are presented, addressing the open question whether all the rules can be efficiently extracted in a single database pass.
Sampling Large Databases for Association Rules
1,079 Citations1996Hannu Toivonen
New algorithms that reduce the database activity considerably by picking a Random sample, to find using this sample all association rules that probably hold in the whole database, and then to verify the results with the rest of the database.
CHARM: An Efficient Algorithm for Closed Itemset Mining
896 Citations2002Mohammed J. Zaki, Ching-Jui Hsiao
CHARM is an efficient algorithm for mining all frequent closed itemsets that enumerates closed sets using a dual itemset-tidset search tree, using an efficient hybrid search that skips many levels, and uses a technique called diffsets to reduce the memory footprint of intermediate computations.
CLOSET : An Efficient Algorithm for Mining Frequent Closed Itemsets
829 Citations2000Jian Pei
Mining association rules with item constraints
769 Citations1997Ramakrishnan Srikant, Quoc Vu +1 more
This work considers the problem of integrating constraints that are Boolean expressions over the presence or absence of items into the association discovery algorithm and presents three integrated algorithms for mining association rules with item constraints and discusses their tradeoffs.
Exploratory mining and pruning optimizations of constrained associations rules
713 Citations1998Raymond T. Ng, Laks V. S. Lakshmanan +2 more
An architecture that opens up the black-box, and supports constraint-based, human-centered exploratory mining of associations, and introduces and analyzes two properties of constraints that are critical to pruning: anti-monotonicity and succinctness.
Knowledge Discovery and Data MiningEfficient algorithms for discovering association rules
630 Citations1994Heikki Mannila, Hannu Toivonen +1 more
An improved algorithm for the problem of mining association rules from large collections of data based on careful combinatorial analysis of the information obtained in previous passes is given, which makes it possible to eliminate unnecessary candidate rules.
MAFIA: a maximal frequent itemset algorithm for transactional databases
610 Citations2002Doug Burdick, Manuel Calimlim +1 more
A new algorithm for mining maximal frequent itemsets from a transactional database that integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms and combines a vertical bitmap representation of the database with an efficient relative bitmap compression schema is presented.
Journal of Parallel and Distributed ComputingA Tree Projection Algorithm for Generation of Frequent Item Sets
506 Citations2001Ramesh C. Agarwal, Charų C. Aggarwal +1 more
This paper provides an implementation of the tree projection method which is up to one order of magnitude faster than other recent techniques in the literature and has a well-structured data access pattern which provides data locality and reuse of data for multiple levels of the cache.
Real world performance of association rule algorithms
491 Citations2001Zijian Zheng, Ron Kohavi +1 more
The experimental results confirm the performance improvements previously claimed by the authors on the artificial data, but some of these gains do not carry over to the real datasets, indicating overfitting of the algorithms to the IBM artificial dataset.
Depth first generation of long patterns
322 Citations2000Ramesh C. Agarwal, Charų C. Aggarwal +1 more
An algorithm for mining long patterns in databases by using depth first search on a lexicographic tree of itemsets achieves more than one order of magnitude speedup over the recently proposed MaxMiner algorithm.
Lecture notes in computer sciencePincer-search: A new algorithm for discovering the maximum frequent set
279 Citations1998Dao-I Lin, Zvi M. Kedem
This work presents a new algorithm which combines both the bottom-up and top-down searches, and produces the maximum frequent set, i.e., the set containing all maximal frequent itemsets, which therefore specifies immediately all frequent itemets.
ACM SIGKDD Explorations NewsletterKDD-Cup 2000 organizers' report
255 Citations2000Ron Kohavi, Carla E. Brodley +3 more
KDD-Cup 2000, the yearly competition in data mining, is described, for the first time the Cup included insight problems in addition to prediction problems, thus posing new challenges in both the knowledge discovery and the evaluation criteria and highlighting the need to "peel the onion" and drill deeper into the reasons for the initial patterns found.
Data Mining and Knowledge DiscoveryFree-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries
253 Citations2003Jean‐François Boulicaut, Artur Bykowski +1 more
The experiments show that the extraction of frequent free-sets can be efficiently extracted using pruning strategies developed for frequent itemset discovery, and that they can be used to approximate the support of any frequent item set.
Mining frequent item sets by opportunistic projection
189 Citations2002Junqiang Liu, Yunhe Pan +2 more
This paper presents a novel algorithm Opportune Project for mining complete set of frequent item sets by projecting databases to grow a frequent item set tree, and proposes novel methods to build tree-based pseudo projections and array-based unfiltered projections for projected transaction subsets.
ACM SIGMOD RecordOptimization of constrained frequent set queries with 2-variable constraints
157 Citations1999Laks V. S. Lakshmanan, Raymond T. Ng +2 more
Adaptive and resource-aware mining of frequent sets
104 Citations2003Salvatore Orlando, P. Palmerini +2 more
DCI (Direct Count & Intersect), an efficient algorithm for discovering frequent sets from large databases, is presented, which can adapt its behavior not only to the features of the specific computing platform, but also to the Features of the dataset being mined, so that it results very effective in mining both short and long patterns from sparse and dense datasets.
Discrete MathematicsA new short proof for the Kruskal-Katona theorem
73 Citations1984Péter Frankl
A very short proof for the Kruskal-Katona theorem and Lovasz's version of it is given: given xkk-element sets there are at least xk - 1 (k- 1)-element sets which are contained in at least one of the k-sets.
Lecture notes in computer scienceOn Supporting Interactive Association Rule Mining
47 Citations2000Bart Goethals, Jan Van den Bussche
This work investigates ways to support interactive mining sessions, in the setting of association rule mining, by a combination of the incorporation of filtering conditions inside the mining phase, and the filtering of already generated associations.
A tight upper bound on the number of candidate patterns
39 Citations2002Floris Geerts, Bart Goethals +1 more
This work provides a tight upper bound for the maximal number of candidate patterns that can be generated on the next level of the standard level-wise algorithm, derived from a combinatorial result by Kruskal and Katona.
arXiv (Cornell University)A Tight Upper Bound on the Number of Candidate Patterns
34 Citations2001Floris Geerts, Bart Goethals +1 more