Method and system for mining quantitative association rules in large relational tables

Patent 5724573 Issued on March 3, 1998. Estimated Expiration Date:

December 22, 2015. 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

System for accessing a row of time-dependent data by referring to a composite index table indicating page locations of linked row labels
Patent #: 5253361
Issued on: 10/12/1993
Inventor: Thurman, et al.

Method and apparatus for transforming objects in data models
Patent #: 5315709
Issued on: 05/24/1994
Inventor: Alston, Jr., et al.

System for data sharing among independently-operating information-gathering entities with individualized conflict resolution rules
Patent #: 5504890
Issued on: 04/02/1996
Inventor: Sanford

Enhanced apparatus and methods for retrieving and selecting profiled textural information records from a database of defined category structures
Patent #: 5537586
Issued on: 07/16/1996
Inventor: Amram, et al.

Multilayered photoreceptor with adhesive and intermediate layers Patent #: 5614341
Issued on: 03/25/1997
Inventor: Mishra, et al.

Inventors

Application

No. 577945 filed on 12/22/1995

US Classes:

707/6, Pattern matching access707/1, DATABASE OR FILE ACCESSING707/3Query processing (i.e., searching)

Examiners

Primary: Amsbury, Wayne

Attorney, Agent or Firm

Tran; Khanh Q., Pintner; James C.

International Class

G06F 017/30

Abstract

A method and apparatus are disclosed for mining quantitative association rules from a relational table of records. The method comprises the steps of: partitioning the values of selected quantitative attributes into intervals, combining adjacent attribute values and intervals into ranges, generating candidate itemsets, determining frequent itemsets, and outputting an association rule when the support for a frequent itemset bears a predetermined relationship to the support for a subset of the frequent itemset. Preferably, the partitioning step includes determining whether to partition and the number of partitions based on a partial incompleteness measure. The candidate generation includes discarding those itemsets not meeting a user-specified interest level and those having a subset which is not a frequent itemset. The frequent itemsets are determined using super-candidates that include information of the candidate itemsets. Preferably, each super-candidate has a data structure, such as a multi-dimensional tree or array, representing quantitative attributes common to the replaced candidate itemsets.

Other References

DeWitt et al, "The Gamma Database Machine Project", IEEE Trans. Knowledge & Data Engineering, Mar., 31, 1990
Mannila et al, "Improved Methods for Finding Association Rules", Pub. No. c-1993-65, Universith Helsinki, 193, Dec. 31, 1993
Park et al, "Eficient Data Mining for Association Rules", IBM Research Report, R210156, Aug. 31, 1995
R. Agrawal, T. Imielinski, A Swami, Mining Association Rules Between Sets of Items in Large Databases, In Proc. of the ACM SIGMOD Conference on Management of Data, pp. 207-216, Washington, D.C. May 1993
R. Agrawal, R. Srikant, Fast Algorithms for Mining Association Rules, In Proc. of the VLDB Conference, Santiago, Chile, pp. 487-499, Sep. 1944
N. Beckmann, H. Kriegel, R. Schneider, B. Seeger, The R*-tree: An Efficient and Robust Access Method for Points and Rectangles, In Proc. of ACM SIGMOD, pp. 322-331, Atlantic City, NJ, May 1990
R. T. NG, J. Han, Efficient and Effective Clustering Methods for Spatial Data Mining, In Proc. of the VLDB Conference, Santiago, Chile, pp. 144-155, Sep. 1994
J. S. Park, M. Chen, P. S. Yu, An Effective Hash-Based Algorithm for Mining Association Rules, In Proc. of the ACM-SIGMOD Conference on Management of Data, pp. 175-186 San Jose, California May 1995
G. P. Shapiro, Discovery, Analysis, and Presentation of Strong Rules, Knowledge Discovery in Databases, pp. 229-248, AAAI/MIT Press, Menlo Park, CA, 1991 (GTE Lab. Incorporated)
M. Houtsma, A. Swami, Set-Oriented Mining for Association Rules, IBM Research Report 9567 (83573), Computer Science, Oct. 22, 1993
R. Srikant, R. Agrawal, Mining Generalized Association Rules, In Proc. of the VLDB Conference, pp. 407-419, Zurich, Switzerland, Sep. 1995
J. Han, Y. Fu, Discovery of Multiple-Level Association Rules from Large Databases, In Proc. of the VLDB Conference, pp. 420-431, Zurich Switzerland, Sep. 1995
A. Savasere, E. Omiecinski, S. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21st VLDB Conference pp. 432-444, Zurich, Switzerland, Sep. 199