Method and apparatus for mining association rules having item constraints

Patent 6061682 Issued on May 9, 2000. Estimated Expiration Date:

August 12, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Concept matching of natural language queries with a database of document concepts
Patent #: 5418948
Issued on: 05/23/1995
Inventor: Turtle

Expert system and method employing hierarchical knowledge base, and interactive multimedia/hypermedia applications
Patent #: 5644686
Issued on: 07/01/1997
Inventor: Hekmatpour

Method and system for mining quantitative association rules in large relational tables
Patent #: 5724573
Issued on: 03/03/1998
Inventor: Agrawal, et al.

Database mining using multi-predicate classifiers
Patent #: 5727199
Issued on: 03/10/1998
Inventor: Chen, et al.

Method and system for mining generalized sequential patterns in a large database
Patent #: 5742811
Issued on: 04/21/1998
Inventor: Agrawal, et al.

System and method for quickly mining association rules in databases
Patent #: 5794209
Issued on: 08/11/1998
Inventor: Agrawal, et al.

System and method for mining sequential patterns in a large database Patent #: 5819266
Issued on: 10/06/1998
Inventor: Agrawal, et al.

Inventors

Assignee

International Business Machines Corporation

Application

No. 910194 filed on 08/12/1997

US Classes:

707/6, Pattern matching access707/1, DATABASE OR FILE ACCESSING707/7, Sorting707/10Distributed or remote access

Examiners

Primary: Lintz, Paul R.
Assistant: Fleurantin, Jean Bolte

Attorney, Agent or Firm

Gray Cary Ware Freidenrich

International Class

G06F 017/30

Abstract

A method for discovering association rules in a database that employs item constraints for extracting desired data relationships from a data base, thereby reducing the execution time of the rule discovery process and increasing the quality of the information returned. Such constraints allow users to specify the subset of rules in which the users are interested. Given a set of transactions D and constraints represented by a boolean expression ଲ, the invention integrates the constraints into a selected rule discovery method rather than implementing the constraints as a post-processing step. The invention quickly discovers association rules that satisfy ଲ and have support and confidence levels greater than or equal to user-specified minimum support and minimum confidence levels, and may be implemented even when a taxonomy is present.

Other References

Toivonen, "Sampling Large Databases for Association Rules," (Univ. of Helsinki) Proc. of the 22nd VLDB Conference, 12 pgs., Mumbai (Bombay), India, 1996
Agrawal et al., "Fast Discovery of Association Rules," Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press,(18 pgs) 1996
Agrawal et al., "Parallel Mining of Association Rules," IEEE Transactions on Knowledge and Data Engineering, vol. 8, No. 6, pp. 962-969, Dec. 1996
Han et al., "Scalable Parallel Data Mining for Association Rules," Pub. No. ACM 0-89791-911-4/97/00005, Proc. of the ACM SIGMOD Conf. on Management of Data, (pp. 277-288) Tucson, AZ, May 1997
Agrawal et al., "Fast Algorithms for Mining Association Rules in Large Databases," Proc. of the VLDB Conference, (pp. 487-499) Santiago, Chile, 1994
Mannila et al., "Improved Method for Finding Association Riles," Pub. No. C-1993-65, 20 pages, Dept. of Computer Science, University of Helsinki, 199