The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.9 pp.1945-1952

- Publication Date
- 1999/09/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Algorithms and Data Structures

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yeon-Dae KWON, Ryuichi NAKANISHI, Minoru ITO, Michio NAKANISHI, "Computational Complexity of Finding Meaningful Association Rules" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 9, pp. 1945-1952, September 1999, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_9_1945/_p

Copy

@ARTICLE{e82-a_9_1945,

author={Yeon-Dae KWON, Ryuichi NAKANISHI, Minoru ITO, Michio NAKANISHI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Computational Complexity of Finding Meaningful Association Rules},

year={1999},

volume={E82-A},

number={9},

pages={1945-1952},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={September},}

Copy

TY - JOUR

TI - Computational Complexity of Finding Meaningful Association Rules

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1945

EP - 1952

AU - Yeon-Dae KWON

AU - Ryuichi NAKANISHI

AU - Minoru ITO

AU - Michio NAKANISHI

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 1999

AB - 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.

ER -