US5920855A
Expired / Lapsed
US
⏱️ 0.0 years remaining
On-line mining of association rules
Assignee: International Business Machines Corp
•
Filing: 1997-06-03
•
Granted: 1999-07-06
•
Expires: 2017-06-03
Abstract
Abstract A computer method of online mining of association rules by pre-processing data within the constraint of available memory. The required computational effort for performing online mining of association rules is reduced by a two-step procedure that involves first creating an adjacency lattice which pre-stores a number of large itemsets at a level of support dictated by available memory. The lattice structure is useful for both finding the itemsets quickly, by reducing the amount of disk I/O required to perform the analysis, and also using the itemsets in order to generate the rules. Once the adjacency lattice is obtained, the second (mining) step is further comprised of two phases. The first phase involves a search algorithm used to find the corresponding itemsets at user specified levels of minimum support. The second phase involves using those itemsets to generate association rules at the user specified level of minimum confidence.
Inventors
- 👤 Charu Chandra Aggarwal
- 👤 Philip Shi-lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:05
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2465; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
149 words
A computer performed process of online mining of a large database having a plurality of records, and each record has a plurality of items for providing association rules comprising the steps of: inputting to the computer, data including user queries, a minimum support level, a minimum confidence level, a f-quantile level; and generating large itemsets based on a predefined criteria constrained by available computer memory; and storing said large itemsets; and constructing in memory a data structure, including large itemsets, an associated support value for each itemset, and adjacency information relating said large itemsets; and selecting those large itemsets from said data structure that satisfy said user queries; and generating association rules from those large itemsets that satisfy said user queries at a minimum support and a minimum confidence; and displaying to a user said association rules; and interactively modifying said user query to further define said association rules.
Claim 2
Dependent Claim
149 words
A computer performed process of online mining of a large database having a plurality of records, and each record has a plurality of items for providing association rules comprising the steps of: inputting to the computer, data including user queries, a minimum support level, a minimum confidence level, a f-quantile level; and generating large itemsets based on a predefined criteria constrained by available computer memory; and storing said large itemsets; and constructing in memory a data structure, including large itemsets, an associated support value for each itemset, and adjacency information relating said large itemsets; and selecting those large itemsets from said data structure that satisfy said user queries; and generating association rules from those large itemsets that satisfy said user queries at a minimum support and a minimum confidence; and displaying to a user said association rules; and interactively modifying said user query to further define said association rules.
Claim 3
Dependent Claim
20 words
A method according to claim 1 where the step of generating large itemsets is based on said minimum support level.
Claim 4
Dependent Claim
93 words
A method according to claim 2 where finding said minimum support level further comprises: generating all large k-itemsets in lexicographic order at some underestimate of said user required support level until the available memory is fully utilized; and resetting said underestimated support level upward to a value defined by said f-quantile value; and pruning all k-itemsets whose associated support value is less than said underestimated support value; and continuing this process until a level of support is achieved that allows all generated k-itemsets to be stored within the available memory of the system.
Claim 5
Dependent Claim
23 words
A method according to claim 2 wherein the step of generating large itemsets further includes generating large itemsets with a plurality of dimensions.
Claim 6
Dependent Claim
22 words
A method according to claim 2 wherein the step of generating large itemsets further includes a hierarchical structure for said large itemsets.
Claim 7
Dependent Claim
28 words
A method according to claim 2 wherein the step of generating large itemsets further includes both a plurality of dimensions and a hierarchical structure for said large itemsets.
Claim 8
Dependent Claim
26 words
A method according to claim 1 where the step of generating large itemsets is based on the largest number of itemsets desired given available computer memory.
Claim 9
Dependent Claim
44 words
A method according to claim 1, wherein the step of prestoring adjacency information further includes the steps of: storing all subsets of large itemsets; and storing pairs of large itemsets such that one itemset can be obtained from another by removing exactly one item.
Claim 10
Dependent Claim
166 words
A computer program device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for computer performed process of online mining of a large database having a plurality of records, and each record having a plurality of items for providing association rules comprising the steps of: inputting to the computer, data including user queries, a minimum support level, a minimum confidence level, a f-quantile level; generating large itemsets based on a predefined criteria constrained by available computer memory and storing said large itemsets; constructing in memory a data structure, including large itemsets, an associated support value for each itemset, and adjacency information relating said large itemsets; selecting those large itemsets from said data structure that satisfy said user queries; generating association rules from those large itemsets that satisfy said user queries at a minimum support and a minimum confidence; displaying to a user said association rules; and interactively modifying said user query to further define said association rules.
Claim 11
Dependent Claim
166 words
A computer program device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for computer performed process of online mining of a large database having a plurality of records, and each record having a plurality of items for providing association rules comprising the steps of: inputting to the computer, data including user queries, a minimum support level, a minimum confidence level, a f-quantile level; generating large itemsets based on a predefined criteria constrained by available computer memory and storing said large itemsets; constructing in memory a data structure, including large itemsets, an associated support value for each itemset, and adjacency information relating said large itemsets; selecting those large itemsets from said data structure that satisfy said user queries; generating association rules from those large itemsets that satisfy said user queries at a minimum support and a minimum confidence; displaying to a user said association rules; and interactively modifying said user query to further define said association rules.
Claim 12
Dependent Claim
22 words
The computer program device according to claim 9 where the step of generating large itemsets is based on said minimum support level.
Claim 13
Dependent Claim
95 words
The computer program device according to claim 10 where finding said minimum support level further comprises: generating all large k-itemsets in lexicographic order at some underestimate of said user required support level until the available memory is fully utilized; and resetting said underestimated support level upward to a value defined by said f-quantile value; and pruning all k-itemsets whose associated support value is less than said underestimated support value; and continuing this process until a level of support is achieved that allows all generated k-itemsets to be stored with the available memory of the system.
Claim 14
Dependent Claim
25 words
The computer program device according to claim 10 wherein the step of generating large itemsets further includes generating large itemsets with a plurality of dimensions.
Claim 15
Dependent Claim
24 words
The computer program device according to claim 10 wherein the step of generating large itemsets further includes a hierarchical structure for said large itemsets.
Claim 16
Dependent Claim
30 words
The computer program device according to claim 10 wherein the step of generating large itemsets further includes both a plurality of dimensions and a hierarchical structure for said large itemsets.
Claim 17
Dependent Claim
28 words
The computer program device according to claim 9 where the step of generating large itemsets is based on the largest number of itemsets desired given available computer memory.
Claim 18
Dependent Claim
46 words
The computer program device according to claim 9, wherein the step of pre-storing adjacency information further includes the steps of: storing all subsets of large itemsets; and storing pairs of large itemsets such that one itemset can be obtained from another by removing exactly one item.
References Cited (Backward Citations)
CA810807A
Cited
US5841437A
Cited
US5664171A
Cited
US5794209A
Cited
US5615341A
Cited
US5758088A
Cited
US5724573A
Cited
EP0855656A2
Cited
US5832482A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-05 | 2003-01-04 | 2003-07-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-05 | 2007-01-04 | 2007-07-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-05 | 2011-01-04 | 2011-07-06 | $7700.00 | Window Closed / Lapsed |