For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational Complexity of Finding Meaningful Association Rules
Yeon-Dae KWON Ryuichi NAKANISHI Minoru ITO Michio NAKANISHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/09/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
data mining, large itemset, meaningful association rule, computational complexity, database,
Full Text: PDF(529.4KB)>>
Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.