A condensed representation to find frequent patterns

Published 1 May 2001

Artur Bykowski, Christophe Rigotti

Citations122

TL;DR

This paper shows that a condensed representation of the frequent patterns called disjunction-free sets can be used to regenerate all frequent patterns and their exact frequencies, and this regeneration can be performed without any access to the original data.

Abstract

Given a large set of data, a common data mining problem is to extract the frequent patterns occurring in this set. The idea presented in this paper is to extract a condensed representation of the frequent patterns called disjunction-free sets, instead of extracting the whole frequent pattern collection. We show that this condensed representation can be used to regenerate all frequent patterns and their exact frequencies.

Keywords

Computer Science

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.

View PDF

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.

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.

Data Mining and Knowledge DiscoveryLevelwise Search and Borders of Theories in Knowledge Discovery

865 Citations1997Heikki Mannila, Hannu Toivonen

The concept of the border of a theory, a notion that turns out to be surprisingly powerful in analyzing the algorithm, is introduced and strong connections between the verification problem and the hypergraph transversal problem are shown.

CLOSET : An Efficient Algorithm for Mining Frequent Closed Itemsets

829 Citations2000Jian Pei

Information SystemsEfficient mining of association rules using closed itemset lattices

739 Citations1999Nicolas Pasquier, Yves Bastide +2 more

Experiments showed that Close is very efficient for mining dense and/or correlated data such as census style data, and performs reasonably well for market basket style data.

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.

View PDF

Lecture notes in computer scienceApproximation of Frequency Queries by Means of Free-Sets

117 Citations2000Jean‐François Boulicaut, Artur Bykowski +1 more

It is shown that frequent free-sets can be efficiently extracted using pruning strategies developed for frequent item-set discovery, and that they can be used to approximate the support of any frequent itemset.

View PDF