Mining Structured Association Patterns from Databases
Lecture notes in computer sciencePublished 1 January 2000
Hirofumi Matsuzawa, Takeshi Fukuda
Citations14
SJR quartileQ2
SJR score0.35
SNIP0.55
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.
TL;DR
This work presents an algorithm that discovers all frequent structured association patterns from large databases, and shows that this method is applicable to a broad range of data mining applications.
Abstract
We consider the data-mining problem of discovering structured association patterns from large databases. A structured association pattern is a set of sets of items that can represent a two level structure in some specified set of target data. Although the structure is very simple, it cannot be extracted by conventional pattern discovery algorithms. We present an algorithm that discovers all frequent structured association patterns. We were motivated to consider the problem by a specific text mining application, but our method is applicable to a broad range of data mining applications. Experiments with synthetic and real data show that our algorithm efficiently discovers structured association patterns in a large volume of data.
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
Mining sequential patterns
5,115 Citations2002R. K. Agrawal, Ramakrishnan Srikant
Three algorithms are presented to solve the problem of mining sequential patterns over databases of customer transactions, and empirically evaluating their performance using synthetic data shows that two of them have comparable performance.
SIAM Journal on ComputingAn $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
2,843 Citations1973John E. Hopcroft, Richard M. Karp
Lecture notes in computer scienceMining sequential patterns: Generalizations and performance improvements
2,686 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
This work adds time constraints that specify a minimum and/or maximum time period between adjacent elements in a pattern, and relax the restriction that the items in an element of a sequential pattern must come from the same transaction.
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.
Future Generation Computer SystemsMining generalized association rules
1,617 Citations1997Ramakrishnan Srikant, Rakesh Agrawal
A new interest-measure for rules which uses the information in the taxonomy is presented, and given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules.
Journal of the ACMA Space-Economical Suffix Tree Construction Algorithm
1,518 Citations1976Edward M. McCreight
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching that has the same asymptotic running time bound as previously published algorithms, but is more economical in space.
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.
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.
Discovery of Multiple-Level Association Rules from Large Databases
920 Citations1995Jiawei Han, Yongjian Fu
A top-down progressive deepening method is developed for mining multiplelevel association rules from large transaction databases by extension of some existing association rule mining techniques.
ACM SIGMOD RecordDynamic itemset counting and implication rules for market basket data
611 Citations1997Sergey Brin, Rajeev Motwani +2 more
Semistructured data
443 Citations1997Peter Buneman
A number of issues surrounding semi-structured data are covered: finding a concise formulation, building a sufficiently expressive language for querying and transformation, and opti-mizat,ion problems.
The COCOON platform (University of Paris)The Japanese government project for machine translation
73 Citations1985Makoto Nagao, Jun’ichi Tsujii +1 more
The purpose is to demonstrate the feasibility of machine translation of abstracts of scientific and engineering papers between the two languages, and as a result, to establish a fast information exchange system for these papers.
Schema discovery for semistructured data
71 Citations1997Ke Wang, Huiqing Liu
This work motivates the schema discovery in this general setting and proposes a framework and algorithm for it and applies the framework to a real Web database, the Internet Movies Database, to discover typical schema of most voted movies.