Please use this identifier to cite or link to this item:
Title: A new concise representation of frequent itemsets using generators and a positive border
Authors: Liu, G. 
Li, J.
Wong, L. 
Keywords: Concise representation
Frequent itemset mining
Positive border
Issue Date: 2008
Citation: Liu, G., Li, J., Wong, L. (2008). A new concise representation of frequent itemsets using generators and a positive border. Knowledge and Information Systems 17 (1) : 35-56. ScholarBank@NUS Repository.
Abstract: A complete set of frequent itemsets can get undesirably large due to redundancy when the minimum support threshold is low or when the database is dense. Several concise representations have been previously proposed to eliminate the redundancy. Generator based representations rely on a negative border to make the representation lossless. However, the number of itemsets on a negative border sometimes even exceeds the total number of frequent itemsets. In this paper, we propose to use a positive border together with frequent generators to form a lossless representation. A positive border is usually orders of magnitude smaller than its corresponding negative border. A set of frequent generators plus its positive border is always no larger than the corresponding complete set of frequent itemsets, thus it is a true concise representation. The generalized form of this representation is also proposed. We develop an efficient algorithm, called GrGrowth, to mine generators and positive borders as well as their generalizations. The GrGrowth algorithm uses the depth-first-search strategy to explore the search space, which is much more efficient than the breadth-first-search strategy adopted by most of the existing generator mining algorithms. Our experiment results show that the GrGrowth algorithm is significantly faster than level-wise algorithms for mining generator based representations, and is comparable to the state-of-the-art algorithms for mining frequent closed itemsets. © Springer-Verlag London Limited 2007.
Source Title: Knowledge and Information Systems
ISSN: 02191377
DOI: 10.1007/s10115-007-0111-5
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Mar 20, 2019


checked on Mar 5, 2019

Page view(s)

checked on Mar 10, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.