US 6,324,533 B1Grant
Integrated database and data-mining system
Issue Date:2001-11-27
•33 Claims
•16 Drawing Sheets
Abstract
A method and apparatus for mining data relationships from an integrated database and data-mining system are disclosed. A set of frequent 1-itemsets is generated using a group-by query on data transactions. From these frequent 1-itemsets and the transactions, frequent 2-itemsets are determined. A candidate set of (n+2)-itemsets are generated from the frequent 2-itemsets, where n=1. Frequent (n+2)-itemsets are determined from candidate set and the transaction table using a query operation. The candidate set and frequent (n+2)-itemset are generated for (n+1) until the candidate set is empty. Rules are then extracted from the union of the determined frequent itemsets.
Metadata
Assignee
- International Business Machines Corporation
Inventors
- Rakesh Agrawal
- Sunita Sarawagi
- Shiby Thomas
Application Information
Application Number:US 09/087,561
Filing Date:1998-05-29
Priority Date:1998-05-29
Art Unit:7
Classifications
IPC:
G06F 1730G06F 700
Field of Search:
707 1707 3707 4707 6705 10706 47706 46
Patent Drawings (16 sheets)
Description
Field of the Invention
[0002] The present invention generally relates to data processing, and more particularly, to a method and system for efficiently mining data relationships from an integrated database and data-mining system.
Background of the Invention
[0003] A recent trend in database applications is the installation of larger and larger data warehouses built around relational database technology in an increasing number of enterprises. There is a great demand for being able to mine nuggets of knowledge from these data warehouses. The initial research on data mining was concentrated on defining new mining operations and developing algorithms for them. Most early mining systems were developed largely on file systems in which specialized data structures and buffer management strategies were devised for each mining algorithm. Coupling data mining with database systems was at best loose, and access to data in a database management system (DBMS) was provided through an Open Database Connectivity (ODBC) interface or a Structured Query Language (SQL) cursor interface. Such an interface is described, for example, in the IBM Intelligent Miner User's Guide, Version 1 Release 1, published by International Business Machines Corp., July 1996. Other interfaces are described by R. Agrawal et al. in the paper “The Quest Data Mining System,” Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Portland, Oreg., August 1996, and by J. Han et al. in “DMQL: A Data Mining Query Language For Relational Databases,” Proc. of the 1996 SIGMOD Workshop on Research Issues on Data mining and Knowledge Discovery, Montreal, Canada, May 1996.
[0004] Recently, researchers have started to focus on issues related to integrating mining with databases, such as proposals to extend the SQL language to support mining operators. For instance, the query language DMQL proposed by Han et al. extends SQL with a collection of operators for mining characteristic rules, discriminant rules, classification rules, association rules, etc. In the paper “Discovery Board Application Programming Interface and Query Language for Database Mining,” Proc. of the 2nd Int'l Conference on Knowledge Discovery and Data Mining, Oregon, August 1996, Imielinski et al. extend M-SQL, which is an extension of the SQL language with a special unified operator to generate and query a whole set of propositional rules. Another example is the mine rule operator proposed by Meo et al. for a generalized version of the association rule discovery problem, described in “A New SQL Like Operator For Mining Association Rules,” Proc. of the 22nd Int'l Conference on Very Large Databases, India, September 1996. Tsur et al. also proposed “query flocks” for data mining using a generate-and-test model, as described in “Query Flocks: A Generalization of Association Rule Mining,” available on the World Wide Web at http://db.stanford.edu/ullman/pub/flocks.ps, October 1997.
[0005] The issue of tightly coupling a mining algorithm with a relational database system from the systems point of view was addressed by R. Agrawal et al. in a paper entitled “Developing Tightly-coupled Data Mining Applications On A Relational Database System,” Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Oregon, August 1996. This proposal makes use of user-defined functions (UDFs) in SQL statements to selectively push parts of the application that perform computations on data records into the database system. The objective here was to avoid one-at-a-time record retrieval from the database to the application address space, saving both the copying and process context switching costs. In the paper entitled “KESO: Minimizing Database Interaction,” Proc. of the 3rd Int'l Conference on Knowledge Discovery and Data Mining, August 1997, A. Siebes et al. focus on developing a mining system with minimal database interaction. Another algorithm for finding association rules, SETM, was expressed in the form of SQL queries and described by M. Houtsma et al. in “Set-oriented Mining of Association Rules,” Proc. of the Int'l Conference on Data Engineering, Taiwan, 1995. However, SETM is not efficient and there are no results reported on running it against a relational DBMS.
[0006] Therefore, there is still a need of a method for efficiently mining data from an integrated database and data-mining system that has a shorter response time, requires less memory to operate, does not suffer the disadvantages discussed in the Background section.
Summary of the Invention
[0007] It is an object of the present invention to provide an efficient method for extracting data relationships from an integrated database and data-mining system.
[0008] Another object of the present invention is to provide a method for mining data relationships from the integrated mining system in the form of queries to SQL engines, and with k-way join, three-way join, subqueries, and group-by operations for counting the itemset support.
[0009] Still another object of the present invention is to provide a method for mining data relationships from the integrated mining system in the form of queries to SQL engines enhanced with object-relational extensions (SQL-OR), such as user-defined functions (UDFs) and table functions.
[0010] The present invention achieves the foregoing and other objects by providing a method for identifying rules from an integrated database and data-mining system, where the system includes a database in the form of a table of transactions and a query engine. The method includes the steps of: a) performing a group-by query on the transaction table to generate a set of frequent 1-itemsets; b) determining frequent 2-itemsets from the frequent 1-itemsets and the transaction table; c) generating a candidate set of (n+2)-itemsets from the frequent (n+1)-itemsets, where n=1; d) determining frequent (n+2)-itemsets from the candidate set of (n+2)-itemsets and the transaction table using a query; e) repeating steps (c) and (d) with n=n+1 until the candidate set is empty; and f) generating rules from the union of the determined frequent itemsets.
[0011] The group-by query preferably includes the steps of counting the number of transactions that contain each item and selecting the items that have a support above a user-specified threshold in determining the frequent 1-itemsets. The support of an item is the number of transactions that contain the item. In determining the frequent 2-itemsets, each 1-itemset is joined with itself and two copies of the transaction table using join predicates. The joining results for a pair of items are grouped together in counting the support of the items in the pair. All 2-itemsets that have a support below a specified threshold are removed from the set of 2-itemsets, resulting in the frequent 2-itemsets.
[0012] Preferably, the candidate (n+2)-itemsets are generated using an (n+2)-way join operation. Also, the frequent (n+2)-itemsets are determined using an (n+3)-way join query on the candidate itemsets and (n+2) copies of the transaction table. Alternatively, the frequent (n+2)-itemsets are determined using cascaded subqueries by: a) selecting distinct first items in the candidate itemsets using a subquery; b) joining the distinct first items with the transaction table; c) cascading (n+1) subqueries where each j-th subquery is a three-way join of the result of the last subquery, distinct j items from the candidate itemsets, and the transaction table; and d) using the results of the last subqueries to determine which of the (n+2)-itemsets are frequent.
[0013] In generating rules from the union of the frequent itemsets, all items from the frequent itemsets are first put into a table F. A set of candidate rules is created from the table Fusing a table function. These candidate rules are joined with the table F, and filtered to remove those that do not meet a confidence criteria.
[0014] In the case where the mining engine is an object-relational engine, the generation of 2-itemsets and (n+1)-itemsets preferably includes: a) selecting from Vertical, GatherCount, and GatherJoin a method that has the best cost for generating the (n+1)-itemsets; b) if the Vertical method is selected, then transforming the transaction table into a vertical format if it is not already transformed; and c) generating the frequent (n+1)-itemsets using the selected method.
[0015] Additional objects and advantages of the present invention will be set forth in the description which follows, and in part will be obvious from the description or may be learned from the practice of this invention. The objects of the invention as described herein may be realized and obtained by means particularly pointed out and distinctly claimed in the appended claims taken in conjunction with the accompanying drawings and detailed specification.
Brief Description of the Drawings
[0016] FIG. 1 is a block diagram of the system in which the methods of mining data, in accordance with the invention, may be practiced.
[0017] FIG. 2 is a simplified block diagram of an integrated database and data-mining system in accordance with the invention.
[0018] FIG. 3 is a flowchart representing the general operation of a basic method for mining data relationships in an integrated database and data-mining system, in accordance with the invention.
[0019] FIG. 4 illustrates the candidate generation using a k-way join, for any k.
[0020] FIG. 5 illustrates the candidate generation using a k-way join, for k=4.
[0021] FIG. 6 illustrates the rule generation query in which a table function is used to generate all possible rules from a frequent itemset.
[0022] FIG. 7 is a flowchart showing further details of the process of determining frequent 2-itemsets (from step 31 of FIG. 3).
[0023] FIG. 8 illustrates a tree diagram of the query in a k-way join.
[0024] FIG. 9 is a flowchart showing further details for the step of determining frequent (n+2)-itemsets (step 33 of FIG. 3) using a subqueries-based approach.
[0025] FIG. 10 illustrates the SQL queries for the GatherJoin method.
[0026] FIG. 11 illustrates the support counting using GatherJoin in the second pass on the data.
[0027] FIG. 12 illustrates a tree diagram for the vertical approach.
[0028] FIGS. 13A-13D are graphs comparing the performance of the four SQL-OR approaches: GatherJoin method and its variants GatherPrune, GatherCount, and Vertical, on four datasets for different support values.
Description of the Preferred Embodiments
[0029] The invention will be described primarily in terms of methods for mining relationships among data items from an integrated system of a database and a data-mining engine. However, persons skilled in the art will recognize that a computing system, which includes suitable programming means for operating in accordance with the methods to be disclosed, also falls within the spirit and scope of the invention. In addition, the invention may also be embodied in a computer program product, such as a diskette, for use with a suitable data processing system. Programming means is also provided for directing the data processing system to execute the steps of the methods of the invention, as embodied in the program product.
[0030] FIG. 1 is a simplified block diagram of a typical computing system 2 in which the methods of the invention may be practiced. In FIG. 1, the system 2 includes one or more data processing apparatus, such as a client computer 3 and a server computer 4. In one intended embodiment, the server computer 4 may be a mainframe computer made by IBM Corp., and use an operating system such as one marketed by IBM Corp. under the name MVS. Alternatively, the server computer 4 may be an IBM RS/6000 workstation running version 3.2.5 of the IBM AIX operating system. The server computer 4 may have a database system such as IBM DB2, or it may have data stored as data files, i.e., flat files, in a data storage medium such as a diskette, disk, or tape. It is to be understood that architectures other than the one shown may be used. For example, the functions of the client computer 3 may be incorporated into the server computer 4, and vice versa.
[0031] As shown, the operating system of the server computer 4 includes a mining kernel 5 which may be executed by a processor within the server computer 4 as a series of computer-executable instructions. These instructions may reside, for example, in the RAM of the server computer 4. Alternatively, the instructions may be contained on a data storage device with a computer readable medium, such as a computer diskette, a DASD array, magnetic tape, optical storage device, or other suitable data storage devices. As an illustrative embodiment, the instructions may be implemented in the C++ computer programming language.
[0032] FIG. 1 shows that, through appropriate data access programs and utilities 6, the mining kernel 5 accesses one or more databases 7 or flat files 8 which contain data transactions. After performing the mining operations in accordance with the invention as described below, the mining kernel 5 outputs patterns it discovers to a mining results depository 9, which can be accessed by the client computer 3.
[0033] Additionally, FIG. 1 shows that the client computer 3 can include a mining kernel interface 10 which, like the mining kernel 5, may be implemented in suitable computer code. Among other things, the interface 10 functions as an input mechanism for establishing certain variables, including the values of the minimum support and time-gap constraints as defined below. Further, the client computer 3 preferably includes an output device 11 for outputting or displaying the mining results. As shown, the output device 11 may include a display monitor 12, a printing device 13, or a data storage medium 14.
[0034] Background
[0035] Some basic concepts of data mining are now described to facilitate the description of the invention which follows.
[0036] 1. Association Rules
[0037] Given a set of transactions, where each transaction is a set of items, an association rule is an expression X→Y, where X and Y are sets of items. See, for example, “Mining Association Rules Between Sets Of Items In Large Databases,” R. Agrawal et al., Proc. of the ACM SIGMOD Conference on Management of Data, pp. 207-216, Washington, D.C., May 1993. The intuitive meaning of such a rule is that transactions in the database which contain the items in X tend to also contain the items in Y. An example of such a rule might be that “30% of transactions that contain beer also contain diapers; 2% of all transactions contain both these items”. Here 30% is called the CONFIDENCE of the rule, and 2% the SUPPORT of the rule. The problem of mining association rules is to find all rules that satisfy a user-specified minimum support and minimum confidence. This problem can be decomposed into two subproblems:
[0038] Find all combinations of items whose support is greater than minimum support. Call those combinations frequent itemsets; and
[0039] Use the frequent itemsets to generate the desired rules. The idea is that if, say, ABCD and AB are frequent itemsets, then it can be determined whether the rule AB→CD holds by computing the ratio r=support(ABCD)/support(AB). The rule holds only if r>minimum confidence. Note that the rule will have minimum support because ABCD is frequent.
[0040] 2. Apriori Method
[0041] The basic Apriori method for finding frequent itemsets makes multiple passes over the data. In the k-th pass it finds all itemsets having k items called the k-itemsets. Each pass consists of two phases. Let Fkrepresent the set of frequent k-itemsets, and Ckthe set of candidate k-itemsets (potentially frequent itemsets). First, in the candidate generation phase, the set of all frequent (k−1)-itemsets, Fk−1, found in the (k−1)-th pass, is used to generate the candidate itemsets Ck. The candidate generation procedure ensures that Ckis a superset of the set of all frequent k-itemsets. The algorithm builds a specialized hash-tree data structure in memory out of Ck. Data is then scanned in the support counting phase. For each transaction, the algorithm determines which of the candidates in Ckare contained in the transaction using the hash-tree data structure and increments their support count. At the end of the pass, Ckis examined to determine which of the candidates are frequent, yielding Fk. The algorithm terminates when Fkor Ck+1becomes empty.
[0042] 3. Input-output formats
[0043] Input format: The transaction table T normally has two column attributes: transaction identifier (tid) and item identifier (item). The number of items per transaction is variable and unknown during table creation time. Thus, alternative schemes may not be convenient. In particular, it is not practical to assume that all items in a transaction appear as different columns of a single tuple because often the number of items per transaction can be more than the maximum number of columns that the database supports. For instance, for one of our real-life datasets the maximum number of items per transaction is 872 and for another it is 700. In contrast, the corresponding average number of items per transaction is only 9.6 and 4.4 respectively.
[0044] Output format: The output is a collection of rules of varying length. The maximum length of these rules is much smaller than the number of items and is rarely more than a dozen. Therefore, a rule is represented as a tuple in a fixed-width table where the extra column values are set to NULL to accommodate rules involving smaller itemsets. The schema of a rule is (item1, . . . , itemk, len, rulem, confidence, support) where k is the size of the largest frequent itemset. The len attribute gives the length of the rule and the rulem attribute gives the position of the→in the rule.
[0045] Mining in an Integrated Database and Data-mining System
[0046] Several configurations for coupling data mining with relational database systems and several methods for identifying rules from such configurations are now described. Persons skilled in the art of computer science will find that these methods may be adapted for mining association rules with hierarchies as well as sequential patterns. Those implemented in SQL offer the advantage of leveraging on existing schemes to make the systems robust, portable, scalable, and highly concurrent, such as indexing and query processing capabilities. Rather than devising specialized parallelizations, one can potentially exploit the underlying SQL parallelization, particularly in a shared-memory multiprocessor (SMP) environment. The DBMS support for checkpointing and space management can be valuable for long-running mining algorithms on huge amounts of data. The development of new algorithms could be faster if expressed declaratively using a few SQL operations.
[0047] FIG. 2 schematically shows the configuration of an integrated database and data-mining system. The mining operation is expressed in some extension of SQL or a graphical language, which are input to preprocessor 21. This preprocessor generates appropriate SQL translations for the mining operation. For example, these SQL translations may be those that are executed by a SQL-92 relational engine 22, or by an object-relational engine 23 having the newer object-relational capabilities for an SQL (SQL-OR). The SQL-92 engine is described by J. Melton et al. in the book entitled “Understanding The New SQL: A Complete Guide,” Morgan and Kauffman, 1992. Object-relational extensions are described by K. Kulkarni et al. in “Object Oriented Extensions in SQL3: A Status Report,” SIGMOD Record, 1994. It is assumed that blobs, user-defined functions, and table functions are available in the object-relational engine. The mining results might be output to a depository 24.
[0048] FIG. 3 is a flow chart showing the general operation of a method for mining data in an integrated database and data-mining system. Start with step 30, a group-by query is performed on the data transactions to generate a set of frequent 1-itemsets. One-itemsets are those having exactly one item each, while an itemset is frequent if the number of transactions containing it is at least at a specified number. At step 31, frequent 2-itemsets are determined from the frequent 1-itemsets and the transaction table. A candidate set of (n+2)-itemsets is next generated in step 32 from the frequent (n+1)-itemsets, where n=1. At step 33, frequent (n+2)-itemsets are generated from the candidate set of (n+2)-itemsets and the transaction table using a query. Steps 32 and 33 are repeated for the next value of n until the candidate set is empty, as shown by step 35. When the candidate set is empty, rules are generated from the union of the determined frequent itemsets in step 36. Further details of the steps in FIG. 3 are now described.
[0049] 1. Candidate generation
[0050] The basic process for finding frequent itemsets proceeds as follows. In each pass k of the algorithm, a candidate itemset set Ckis generated from frequent itemsets Fk−1of the previous pass. Given the set of all frequent (k−1)-itemsets, Fk−1, the candidate generation procedure returns a superset of the set of all frequent k-itemsets. The items in an itemset are assumed to be lexicographically ordered. Since all subsets of a frequent itemset are also frequent, the candidate itemset set Ckcan be generated from Fk−1as follows:
[0051] First, in the join step, a superset of the candidate itemsets Ckis generated by joining Fk−1with itself, as shown in the following pseudo code:
[0052] insert into Ckselect I1.item1, . . . , I1.itemk−1, I2.itemk−1
[0053] from Fk−1I1, Fk−1I2
[0054] where I1.item1=I2.item1and
[0055] I1.itemk−2=I2.itemk−2and
[0056] I1.itemk−1<I2.itemk−1
[0057] For example, let F3be {{1 2 3}, {1 2 4}, {1 3 4}, {1 3 5}, {2 3 4}}. After the join step, C4will be {{1 2 3 4}, {1 3 4 5}}.
[0058] Next, in the prune step, all itemsets cε Ck, where some (k−1)-subset of c is not in Fk−1, are deleted. Continuing with the example above, the prune step will delete the itemset {1 3 4 5} because the subset {1 4 5} is not in F3. C4is then left with only {1 2 3 4}. The prune step can be done in the same SQL statement as the join step above by writing it as a k-way join as shown in FIG. 4. A k-way join is used since for any k-itemset there are k subsets of length (k−1) for which we need to check in Fk−1for membership. The join predicates on I1and I2remain the same. After the join between I1and I2we get a k itemset consisting of (I1.item2, I1.item1, . . . I1.itemk−1, I2.itemk−1) as shown above. For this itemset, two of its (k−1)-length subsets are already known to be frequent since it was generated from two itemsets in Fk−. The remaining k−2 subsets are checked using additional joins. The predicates for these joins are enumerated by skipping one item at a time from the k-itemset as follows: item, is skipped and the subset (I1.item2, . . . , I1.itemk−1, I2.itemk−1) is checked to see if it belongs to Fk−1as shown by the join with 13 in the figure. In general, for a join with Iritem r−2 is skipped. FIG. 5 shows an example of the candidate generation for k=4.
[0059] A primary index is constructed on (item1, . . . , itemk−1,) of Fk−1to efficiently process these k-way joins using index probes. Note that sometimes it may not be necessary to materialize Ckbefore the counting phase. Instead, the candidate generation can be pipelined with the subsequent SQL queries used for support counting.
[0060] 2. Counting support to find frequent itemsets
[0061] The candidate itemsets Ckand data table T are used for counting the support of the itemsets in Ck. Two SQL categories may be used:
[0062] 1. SQL-92: Four preferred embodiments based on SQL-92 will described below in section 4.
[0063] 2. SQL object-relational extensions (SQL-OR): Five preferred embodiments based on SQL-OR extensions like user-defined functions (UDFs), binary large objects (BLOBs), and table functions, will be described below in section 5. Table functions are virtual tables associated with a user defined function which generate tuples on the fly. See, for example, “Extensions To Starburst: Objects, Types, Functions, and Rules,” G. Lohman et al., Communications of the ACM, 34(10), October 1991. Like normal physical tables, they have pre-defined schemas. The function associated with a table function can be implemented as any other UDF. Thus, table functions can be viewed as UDFs that return a collection of tuples instead of scalar values.
[0064] 3. Rule generation
[0065] In order to generate rules having minimum confidence (minconf), all non-empty proper subsets of every frequent itemset/are determined. For each subset m, a confidence of the rule m→(I−m) is derived. This rule is then output if it satisfies at least minconf.
[0066] In the support counting phase, the frequent itemsets of size k are stored in table Fk. Before the rule generation phase, all the frequent itemsets are merged into a single table F. The schema of F consists of k+2 attributes (item1, . . . , itemk, support, len), where k is the size of the largest frequent itemset and len is the length of the itemset.
[0067] A table function, GenRules, is used to generate all possible rules from a frequent itemset. The input to the function is a frequent itemset. For each itemset, it outputs tuples corresponding to rules with all non-empty proper subsets of the itemset in the consequent. The table function outputs tuples with k+3 attributes, T_item1, . . . , T_itemk, T_support, T_ten, T_rulem). The output is joined with F to find the support of the antecedent and the confidence of the rule is calculated by taking the ratio of the support values. FIG. 6 illustrates the rule generation query process, while the following pseudo-code shows a typical implementation of this step.
[0068] insert into R select T_item1, . . . , T_itemk, t1.support, T_len, T_rulem, t1.support/f2.support
[0069] from F f1, table(GenRules(f1.item1, . . . , f1.itemk, f1.len, f1.support)) as t1, F f2where (t1.T_item1=f2.item1or t1.T_rulem>1)
[0070] AND (t1.T_itemk=f2.itemkor t1.T_rulem>k)
[0071] AND t1.T_rulem=f2.len
[0072] AND t1/T_support/f2.support>minconf
[0073] The above rule generation can also be done using SQL-92 and without the table functions. The rules are generated in a level-wise manner in which rules are generated with consequents of size k in each level k. Further, for any frequent itemset, if a rule with consequent c holds then so do rules with consequents that are subsets of c. With this property, the rules in level k are formed using rules with (k−1) long consequents found in the previous level, as in the previously described candidate generation.
[0074] 4. Support Counting Using SQL-92
[0075] There are four approaches to counting support with an SQL-92 engine.
[0076] a) K-way joins
[0077] In each pass k, the candidate itemsets Ckis joined with k transaction tables T. This is followed by a group-by operation on the itemsets as shown by the following pseudo-code.
[0078] insert into Fkselect item1, . . . , itemk, count(*)
[0079] from Ck, T1, . . . T tk
[0080] where t1.item=Ck.item1and
[0081] tk.item=Ck.itemkand
[0082] t1.tid=t2.tid and
[0083] tk−1.tid=tk.tid
[0084] group by item1, item2. . . itemk
[0085] having count(*)>minsup
[0086] For the second pass, a special optimization is used where instead of materializing C2, it is replaced with the 2-way joins between the two copies of F1. This saves the cost of materializing C2and also provides early filtering of the T based on F1instead of the larger C2. In contrast, for other passes corresponding to k>2, Ckcould be smaller than Fk−1because of the prune step. FIG. 7 is a flowchart showing further details of the process of determining frequent 2-itemsets (from step 31 of FIG. 3), while FIG. 8 shows a tree diagram of the query. This tree diagram is not to be confused with the plan trees which could look quite different. This SQL computation, when merged with the candidate generation step, can be used as a possible mechanism to implement query flocks.
[0087] b) Three-way joins
[0088] The above approach requires (k+1)-way joins in the k-th pass. The cardinality of joins can be reduced to 3 using the following approach. Each candidate itemset Ck, in addition to attributes (item1, . . . , itemk) has three new attributes (oid, id1, id2). oid is a unique identifier associated with each itemset, and id1and id2are oids of the two itemsets in Fk−1from which the itemset in Ckwas generated. In addition, in the k-th pass a new copy of the data table Tkwith attributes (tid, oid) is generated that keeps for each tid the oid of each itemset in Ckthat it supported. For support counting, Tkis first generated from Tk−1and Ck. A group-by operation is performed on Tkto find Fkas follows:
[0089] insert into Tkselect t1.tid, oid
[0090] from Ck, Tk−1t1, Tk−1t2
[0091] where t1.oid=Ck.id1and t1.oid=Ck.id2and t1.tid=t2.tid
[0092] insert into Fkselect oid, item1, . . . itemk, cnt
[0093] from Ck,
[0094] (select oid as cid, count(*) as cnt from Tk
[0095] group by oid having count(*)>minsup) as temp
[0096] where Ck.oid=cid
[0097] c) Subquery-based
[0098] This approach makes use of common prefixes between the itemsets in Ckto reduce the amount of work done during support counting. The support counting phase is broken into a cascade of k subqueries. The l-th subquery Qlfinds all tids that match the distinct itemsets formed by the first l columns of Ck(call it dl). The output of Qlis joined with T and dl+1(the distinct itemsets formed by the first l+1 columns of Ck) to get Ql+1. The final output is obtained by doing a group-by on the k items to count support as above. For k=2, the same query as in the k-join approach is used. FIG. 9 is a flowchart showing further details for the step of determining frequent (n+2)-itemsets, while the following pseudo-code represents a typical implementation of this step.
[0099] insert into Fkselect item1, . . . itemk, count(*)
[0100] from (Subquery Qk) t
[0101] group by item1, item2. . . itemk
[0102] having count(*)>:minsup
[0103] Subquery Ql(for any l between 1 and k):
[0104] select item1. . . iteml, tid
[0105] from T tl, (Subquery Ql−1) as rl−1,
[0106] (select distinct item1. . . item, from Ck) as dl
[0107] where rl−1.item1=dl.item1and . . . and
[0108] rl−1.iteml−1=dl.iteml−1and
[0109] rl−1.tid=tl.tid and
[0110] tl.item=dl.iteml
[0111] Subquer Q0: No subquery
[0112] d) Two group-bys
[0113] This approach avoids the multi-way joins used in the previous approaches, by joining T and k based on whether the “item” of a (tid, item) pair of T is equal to any of the k items of Ck. Then, do a group by on (item1, . . . , itemk, tid) filtering tuples with count equal to k. This gives all (itemset, tid) pairs such that the tid supports the itemset. Finally, as in the previous approaches, do a group-by on the itemset (item1, . . . , itemk) filtering tuples that meet the support condition.
[0114] insert into Fkselect item1, . . . , itemk, count(*)
[0115] from (select item1, . . . , itemk, count(*)
[0116] from T, Ck
[0117] where item=Ck.item1or
[0118] item=Ck.itemk
[0119] group by item1, . . . , itemk, tid
[0120] having count(*)=k) as temp
[0121] group by item1, . . . , itemk
[0122] having count(*)>minsup
[0123] 5. Support Counting Using SQL With Object-Relational Extensions
[0124] The performance of an integrated database and data-mining system may be further improved using additional object-relational extensions to SQL for counting the itemset support. Such a method, called GatherJoin, and its variants, GatherCount, GatherPrune, and Horizontal, are now described.
[0125] a) GatherJoin
[0126] This approach is based on the use of table functions described above. It generates all possible k-item combinations of items contained in a transaction, joins them with the candidate table Ck, and counts the support of the itemsets by grouping the join result. Two table functions, Gather and Comb-K, are used. The data table T is scanned in the (tid, item) order and passed to the table function Gather. This table function collects all the items of a transaction (in other words, items of all tuples of T with the same tid) in memory and outputs a record for each transaction. Each such record consists of two attributes, the tid and item-list which is a collection of all its items in a VARCHAR or a BLOB. The output of Gather is passed to another table function Comb-K which returns all k-item combinations formed out of the items of a transaction. A record output by Comb-K has k attributes T_itm1, . . . , T_itmk, which can be directly used to probe into the Cktable. An index is constructed on all the items of Ckto make the probe efficient. FIG. 10 illustrates the SQL queries for the GatherJoin approach.
[0127] This approach is analogous to the K-way Join approach where the k-way self join of T is replaced with the table functions Gather and Comb-K. It is possible to merge these functions together as a single table function GatherComb-K. The Gather function is not required when the data is already in a horizontal format where each tid is followed by a collection of all its items. The pseudo-code below illustrate a typical implementation of GatherJoin approach for counting support.
[0128] insert into Fkselect item1, . . . , itemk, count(*)
[0129] from Ck,
[0130] (select t2.T_itm1, . . . , t2.T_itmkfrom T,
[0131] table (Gather(T.tid, T.item)) as t1,
[0132] table (Comb-K(t1.tid, t1.item-list)) as t2)
[0133] where t2.T_itm1=Ck.item1and
[0134] t2.T_itmk=Ck.itemk
[0135] group by Ck.item1, . . . , Ck.itemk
[0136] having count(*)>minsup
[0137] Note that for k=2, the 2-candidate set C2is simply a join of F1with itself. Accordingly, the pass 2 can be optimized by replacing the join with C2by a join with F1before the table function (see FIG. 10). That way, the table function gets only frequent items and generates significantly fewer 2-item combinations. This optimization can be useful for other passes too, but unlike for pass 2, they still require a join with Ck. FIG. 11 illustrates the support counting using GatherJoin in the second pass on the data. The pseudo-code for a typical implementation of the second-pass optimization is as follows.
[0138] insert into Fkselect t1.item, t2.item, cnt
[0139] from (select item1, item2, CountIntersect(t1.tid-list, t2.tid-list) as cnt
[0140] from TidTable t1, TidTable t2
[0141] where t1.item<t2.item) as t
[0142] where cnt>:minsup
[0143] b) Variations of GatherJoin
[0144] GatherCount: One variation of the GatherJoin approach for pass two is the GatherCount approach where the group-by is performed inside the table function instead of doing it outside. The candidate 2-itemsets (C2) are represented as a two dimensional array inside the modified table function Gather-Cnt for doing the support counting. Instead of outputting the 2-item combinations of a transaction, it directly uses it to update support counts in the memory and output only the frequent 2-itemsets, F2and their support after the last transaction. Thus, the table function Gather-Cnt is an extension of the GatherComb-2 table function used in GatherJoin. The absence of the outer grouping makes this option an attractive solution. The UDF code is also small since it only needs to maintain a 2-dimension array. It can be applied for subsequent passes but for the added complexity of maintaining hash-tables to index the Cks itemset. The disadvantage of this approach is that it can require a large amount of memory to store C2. If enough memory is not available, C2needs to be partitioned and the process has to be repeated for each partition.
[0145] Gather Prune: A potential disadvantage of GatherJoin is the high cost of joining the large number of item combinations with Ck. The join with Ckcan be done in the table function to reduce the number of such combinations. Ckis converted to a BLOB and passed as an argument to the table function. The cost of passing the BLOB for every tuple of R could be high. However, the parameter passing cost can be reduced by using a smaller BLOB that only approximates the real Ck. The trade-off is increased cost for other parts notably grouping because not as many combinations are filtered.
[0146] Horizontal: Another variation of GatherJoin is the Horizontal approach that first uses the Gather function to transform the data to the horizontal format but is otherwise similar to the GatherJoin approach.
[0147] The choice of the best SQL-OR approach depends on a number of data characteristics like the number of items, total number of transactions, average length of a transaction etc. The costs of different approaches in each pass can be determined in terms of parameters that are known or can be estimated after the candidate generation step of each pass, as defined in Table 1 below. The cost of GatherJoin includes the cost of generating k-item combinations, joining with Ck, and grouping to count the support. The number of k-item combinations generated is C(N, k)*T. The join with Ckfilters out the non-candidate item combinations. The size of the join result is the sum of the support of all the candidates denoted by
[0148] S(Ck). The actual value of the support of a candidate itemset will be known only after the support counting phase. The total cost of the GatherJoin approach is found as:
[0149] Tk*Sk+join(Tk, CkS(Ck))+group(S(Ck),Ck), where Tk=C(N,k))*T
[0150] This cost needs to be modified to reflect the special optimization of joining with F1 to consider only frequent items. For the second pass, the total cost of GatherJoin is:
[0151] The cost of GatherCount in the second pass is similar to that for basic GatherJoin except for the final grouping cost:
[0152] join(R,F1,Rf)+group_internal(T2,C2)+F2*S2,
[0153] where “group_int” denotes the cost of doing the support counting inside the table function.
[0154] For GatherPrune, the cost is computed as:
[0155] R*blob(k*Ck)+S(Ck)*sk+group(S(Ck), Ck).
[0156] where Blob(k*Ck) denotes the BLOB passing cost since each itemset in Ckcontains k items.
[0157] The cost estimate of the Horizontal method is similar to that of GatherJoin except that here the data is materialized in the horizontal format before generating the item combinations.
[0158] c) Vertical
[0159] In this approach, the data table is first transformed into a vertical format by creating for each item a BLOB containing all tids that contain that item (Tid-list creation phase) and then count the support of itemsets by merging together these tid-lists (support counting phase).
[0160] A table function Gather is used for creating the Tid-lists. This is the same as the Gather function in GatherJoin except here, the tid-list is created for each frequent item. The data table T is scanned in the (item, tid) order and passed to the function Gather. The function collects the tids of all tuples of T with the same item in memory and outputs a (item, tid-list) tuple for items that meet the minimum support criterion. The tid-lists are represented as BLOBs and stored in a new TidTable with attributes (item, tid-list).
[0161] In the support counting phase, conceptually for each itemset in Ckthe tid-lists of all k items are collected and the number of tids in the intersection of these k lists is counted using a user defined function (UDF). The tids are in the same sorted order in all the tid-lists and therefore the intersection can be done easily and efficiently by a single pass of the k lists. This conceptual step can be improved further by decomposing the intersect operation so that we can share these operations across itemsets having common prefixes as follows:
[0162] First, distinct pairs of items (item1, item2) are selected from Ck. For each distinct pair, an intersect operation is performed to get a new result-tidlist. Distinct triples (item1, item2,item3) are then determined from Ckwith the same first two items. The result-tidlist is intersected with tid-list for item3 for each triple, then with item4and so on until all k tid-lists per itemset are intersected.
[0163] The above sequence of operations can be implemented as a single SQL query for any k, as shown in FIG. 12 and the following pseudo-code for Subquery Q1(select*from TidTable). The final intersect operation can be merged with the count operation to return a count instead of the tid-list. To simplify the illustration of the example, this optimization is omitted from the query in this pseudo-code.
[0164] insert into Fkselect item1, . . . , itemk, count(tid-list) as cnt
[0165] from (Subquery Qk) t where cnt>:minsup
[0166] Subquery Ql(for any l between 2 and k):
[0167] select item1, . . . , iteml,
[0168] Intersect (rl−1.tid-list, t1.tid-list) as tid-list
[0169] from TidTable t1, (Subquery Ql−1) as rl−1,
[0170] (select distinct item1, . . . itemlfrom Ck) as dl
[0171] where rl−1.item1=dl.item1and . . . and
[0172] rl−1.iteml−1=dl.iteml−1, and
[0173] tl.item=dl.iteml
[0174] Special pass 2 optimization: For pass 2, it is not necessary to generate C2and join it with the TidTable. Instead, self-join is performed on the TidTable using predicate t1.item<t2.item, as shown in the following pseudo-code.
[0175] insert into Fkselect t1.item, t2.item, cnt
[0176] from (select item1, item2, Count_Intersect(t1.tid-list, t2.tid-list) as cnt
[0177] from TidTable t1, TidTable t2
[0178] where t1.item<t1.item) as t
[0179] where cnt>minsup
[0180] The cost of the Vertical approach during support counting phase is dominated by the cost of invoking the UDFs and intersecting the tid-lists. The UDF is first called for each distinct item pair in Ck, then for each distinct item triple with the same first two items and so on. Let djkbe the number of distinct j item tuples in Ck. Then the total number of times the UDF is invoked is
[0181] In each invocation two BLOBs of tid-list are passed as arguments. The UDF intersects the tid-lists by a merge pass and hence the cost is proportional to 2*average length of a tid-list. The average length of a tid-list can be approximated to Rf_F1. Note that with each intersect the tid-list keeps shrinking. The total cost of the Vertical approach is:
[0182] In formula (x), Intersect(n) denotes the cost of intersecting two tid-lists with a combined size of n. The join cost are not included in this analysis because it accounts for only a small fraction of the total cost.
[0183] The total cost of the second pass is:
[0184] Performance Evaluation
[0185] The performance results for mining boolean association rules using the above methods are now described. The results for mining generalized association rules and sequential patterns are similar. All of the experiments were performed on Version 5 of IBM DB2 Universal Server installed on a RS/6000 Model 140 with a 200 MHz CPU, 256 MB main memory and a 9 GB disc with a measured transfer rate of 8 MB/s. A collection of four real-life datasets were used. These datasets have differing values of parameters like the total number of (tid,item) pairs, the number of transactions (tids), the number of items and the average number of items per transaction. Table 2 summarizes these parameters.
[0186] A composite index (item1, . . . , itemk) is built on Ck, k different indices on each of the k items of Ckand a (tid, item) and a (item, tid) index on the data table. The index building cost is not reflected in the total time.
[0187] The Subquery method was found to be best SQL-92 approach, which was often more than an order of magnitude better than the other three approaches. However, this approach was comparable to the loose-coupling approach only in some cases whereas for several others it did not complete even after taking ten times more time than the loose-coupling approach.
[0188] FIGS. 13A-13D show the performance of the four SQL-OR approaches: GatherJoin method and its variants GatherPrune, GatherCount, and Vertical, on four datasets for different support values. Overall, the Vertical approach has the best performance and is sometimes more than an order of magnitude better than the other three approaches. The majority of the time of the Vertical approach is spent in transforming the data to the Vertical format in most. The vertical representation is like an index on the item attribute. Its performance is even better if this time is viewed as a one-time activity like index building.
[0189] The time taken is broken down by each pass and an initial “prep” stage where any one-time data transformation cost is included. Note that the time to transform the data to the Vertical format was much smaller than the time for the horizontal format although both formats write almost the same amount of data. The main reason was the difference in the number of records written. The number of frequent items is often two to three orders of magnitude smaller than the number of transactions.
[0190] Between GatherJoin and GatherPrune, neither strictly dominates the other. The special optimization in GatherJoin of pruning based on F1 had a big impact on performance. When these different approaches are compared based on the time spent in each pass, no single approach is “the best” for all different passes of the different datasets especially for the second pass. For pass three onwards, Vertical is often two or more orders of magnitude better than the other approaches. Two factors that affect the choice amongst the Vertical, GatherJoin and GatherCount approaches in different passes and pass 2 in particular are: number of frequent items (F1) and the average number of frequent items per transaction (Nf).
[0191] As a hybrid of the SQL-OR methods, the best of the GatherJoin, GatherCount, and Vertical approaches can be selected for each pass based on the cost estimation. The parameter values used for the estimation are all available at the end of the previous pass.
[0192] Impact of longer names: In this study, it is assumed that the tids and item ids are all integers. Often in practice these are character strings longer than four characters. The two (already expensive) steps that could suffer because of longer names are (1) final group-bys during pass 2 or higher when the GatherJoin approach is chosen and (2) tid-list operations when the Vertical approach is chosen. For efficient performance, the first step requires a mapping of item ids and the second one requires us to map tids. A table function is used to map the tids to unique integers efficiently in one pass and without making extra copies. The input to the table function is the data table in the tid order. The table function remembers the previous tid and the maintains a counter. Every time the tid changes, the counter is incremented. This counter value is the mapping assigned to each tid. The tid mapping is only needed to be done once before creating the TidTable in the Vertical approach. These two steps therefore can be pipelined. The item mapping is done slightly differently. After the first pass, a column is added to F1 containing a unique integer for each item, and similarly for the TidTable. The GatherJoin approach already joins the data table T with F1 before passing to table function Gather. Therefore, the integer mappings of each item can be passed to GatherJoin from F1 instead of its original character representation. After these two transformations, the tid and item fields are integers for all the remaining queries including candidate generation and rule generation. By mapping the fields this way, the longer names are expected to have similar performance impact on all of the described options.
[0193] Summary
[0194] Various preferred embodiments for an integrated mining and database system have been described, using association rule mining as an example. Some of the embodiments are implemented using SQL-92 while others are constructed using new object-relational extensions like UDFs, BLOBs, Table functions etc. The integrated systems built with the extended SQL provide orders of magnitude improvement over the SQL-92 based-implementations.
[0195] While several preferred embodiments of the invention have been described, it should be apparent that modifications and adaptations to those embodiments may occur to persons skilled in the art without departing from the scope and the spirit of the present invention as set forth in the following claims.
Claims
What is claimed is:
1. A method for mining rules from an integrated database and data-mining system having a table of data transactions and a query engine, the method comprising the steps of:
a) performing a group-by query on the transaction table to generate a set of frequent 1-itemsets;
b) determining frequent 2-itemsets from the frequent 1-itemsets and the transaction table;
c) generating a candidate set of (n+2)-itemsets from the frequent (n+1)-itemsets, where n=1;
d) determining frequent (n+2)-itemsets from the candidate set of (n+2)-itemsets and the transaction table using a query operation;
e) repeating steps (c) and (d) with n=n+1 until the candidate set is empty; and
f) generating rules from the union of the determined frequent itemsets.
2. The method as recited in claim 1, wherein:
each transaction corresponds to a plurality of items; and
the step of performing a group-by query includes the steps of counting the number of transactions that contain each item and selecting the items that have a support above a user-specified threshold in determining the frequent 1-itemsets, the support of an item being the number of transactions that contain the item.
3. The method as recited in claim 1, wherein the frequent 2-itemsets are generated using a join query.
4. The method as recited in claim 3, wherein the step of determining frequent 2-itemsets includes the steps of:
joining an 1-itemset with itself and two copies of the transaction table using join predicates;
grouping results of the joining step for a pair of items to count the support of the items in the pair; and
removing all 2-itemsets having a support below a specified threshold.
5. The method as recited in claim 1, wherein the candidate (n+2)-itemsets are generated using an (n+2)-way join operation.
6. The method as recited in claim 1, wherein the frequent (n+2)-itemsets are determined using an (n+3)-way join query, on the candidate itemsets and (n+2) copies of the transaction table.
7. The method as recited in claim 1, wherein:
the frequent (n+2)-itemsets are determined using cascaded subqueries; and
the step of determining frequent (n+2)-itemsets includes the steps of:
selecting distinct first items in the candidate itemsets using a subquery;
joining the distinct first items with the transaction table;
cascading (n+1) subqueries where each j-th subquery is a three-way join of the result of the last subquery, distinct j items from the candidate itemsets, and the transaction table; and
determining which of the (n+2)-itemsets are frequent using the results of the last subqueries.
8. The method as recited in claim 1, wherein the step of generating rules includes the steps of:
putting all items from the frequent itemsets into a table F;
generating a set of candidate rules from the table F using a table function;
joining the candidate rules with the table F; and
filtering out from the candidate rules those that do not meet a confidence criteria.
9. The method as recited in claim 1, wherein:
the query engine is an object-relational engine; and
the steps of generating 2-itemsets and (n+1)-itemsets include the steps of:
selecting from Vertical, GatherCount, and GatherJoin a method having the best cost for generating the (n+1)-itemsets;
if the Vertical method is selected, then transforming the transaction table into a vertical format; and
generating the frequent (n+1)-itemsets using the selected method.
10. The method as recited in claim 9 wherein the cost for generating the itemsets is based on statistics about the data transactions and the candidate itemsets.
11. The method as recited in claim 1, wherein the query engine is an SQL engine.
12. An integrated data-mining system comprising:
a database having a table of data transactions;
a query engine coupled to the database;
a query preprocessor for generating queries and input parameters for the query engine;
means for performing a group-by query on the transaction table to generate a set of frequent 1-itemsets;
means for determining frequent 2-itemsets from the frequent 1-itemsets and the transaction table;
means for generating a candidate set of (n+2)-itemsets from the frequent (n+1)-itemsets, where n=1;
means for determining frequent (n+2)-itemsets from the candidate set of (n+2)-itemsets and the transaction table using a query having cascaded subqueries;
means for repeatedly generating the candidate set of (n+2)-itemsets and determining frequent (n+2)-itemsets with n=n+1 until the candidate set is empty; and
means for generating rules from the union of the determined frequent itemsets.
13. A computer program product for mining rules from an integrated database and data-mining system having a table of data transactions and a query engine, the product comprising:
a) means, recorded on the recording medium, for directing the system to perform a group-by query on the transaction table to generate a set of frequent 1-itemsets;
b) means, recorded on the recording medium, for directing the system to determine frequent 2-itemsets from the frequent 1-itemsets and the transaction table;
c) means, recorded on the recording medium, for directing the system to generate a candidate set of (n+2)-itemsets from the frequent (n+1)-itemsets, where n=1;
d) means, recorded on the recording medium, for directing the system to determine frequent (n+2)-itemsets from the candidate set of (n+2)-itemsets and the transaction table using a query operation;
e) means, recorded on the recording medium, for directing the system to repeatedly generate the candidate set of (n+2)-itemsets and determine frequent (n+2)-itemsets with n=n+1 until the candidate set is empty; and
f) means, recorded on the recording medium, for directing the system to generate rules from the union of the determined frequent itemsets.
14. The data-mining system as recited in claim 12, wherein:
each transaction corresponds to a plurality of items; and
the means for performing a group-by query includes means for counting the number of transactions that contain each item and selecting the items that have a support above a user-specified threshold in determining the frequent 1-itemsets, the support of an item being the number of transactions that contain the item.
15. The data-mining system as recited in claim 12, wherein the frequent 2-itemsets are generated using a join query.
16. The data-mining system as recited in claim 15, wherein the means for determining frequent 2-itemsets includes:
means for joining an 1-itemset with itself and two copies of the transaction table using join predicates;
means for grouping results of the joining step for a pair of items to count the support of the items in the pair; and
means for removing all 2-itemsets having a support below a specified threshold.
17. The data-mining system as recited in claim 12, wherein the candidate (n+2)-itemsets are generated using an (n+2)-way join operation.
18. The data-mining system as recited in claim 12, wherein the frequent (n+2)-itemsets are determined using an (n+3)-way join query, on the candidate itemsets and (n+2) copies of the transaction table.
19. The data-mining system as recited in claim 12, wherein:
the frequent (n+2)-itemsets are determined using cascaded subqueries; and
the means for determining frequent (n+2)-itemsets includes:
means for selecting distinct first items in the candidate itemsets using a subquery;
means for joining the distinct first items with the transaction table;
means for cascading (n+1) subqueries where each j-th subquery is a three-way join of the result of the last subquery, distinct j items from the candidate itemsets, and the transaction table; and
means for determining which of the (n+2)-itemsets are frequent using the results of the last subqueries.
20. The data-mining system as recited in claim 12, wherein the means for generating rules includes:
means for putting all items from the frequent itemsets into a table F;
means for generating a set of candidate rules from the table F using a table function;
means for joining the candidate rules with the table F; and
means for filtering out from the candidate rules those that do not meet a confidence criteria.
21. The data-mining system as recited in claim 12, wherein:
the query engine is an object-relational engine; and
the means for generating 2-itemsets and (n+1)-itemsets include:
means for selecting from Vertical, GatherCount, and GatherJoin a method having the best cost for generating the (n+1)-itemsets;
if the Vertical method is selected, then means for transforming the transaction table into a vertical format; and
means for generating the frequent (n+1)-itemsets using the selected method.
22. The data-mining system as recited in claim 21, wherein the cost for generating the itemsets is based on statistics about the data transactions and the candidate itemsets.
23. The data-mining system as recited in claim 12, wherein the query engine is an SQL engine.
24. The product as recited in claim 13, wherein:
each transaction corresponds to a plurality of items; and
the means for directing to perform a group-by query includes means, recorded on the recording medium, for directing the system to count the number of transactions that contain each item and selecting the items that have a support above a user-specified threshold in determining the frequent 1-itemsets, the support of an item being the number of transactions that contain the item.
25. The product as recited in claim 13, wherein the frequent 2-itemsets are generated using a join query.
26. The product as recited in claim 25, wherein the means for directing to determine frequent 2-itemsets includes:
means, recorded on the recording medium, for directing the system to join an 1-itemset with itself and two copies of the transaction table using join predicates;
means, recorded on the recording medium, for directing the system to group results of the joining step for a pair of items to count the support of the items in the pair; and
means, recorded on the recording medium, for directing the system to remove all 2-itemsets having a support below a specified threshold.
27. The product as recited in claim 13, wherein the candidate (n+2)-itemsets are generated using an (n+2)-way join operation.
28. The product as recited in claim 13, wherein the frequent (n+2)-itemsets are determined using an (n+3)-way join query, on the candidate itemsets and (n+2) copies of the transaction table.
29. The product as recited in claim 13, wherein:
the frequent (n+2)-itemsets are determined using cascaded subqueries; and
the means for directing to determine frequent (n+2)-itemsets includes:
means, recorded on the recording medium, for directing the system to select distinct first items in the candidate itemsets using a subquery;
means, recorded on the recording medium, for directing the system to join the distinct first items with the transaction table;
means, recorded on the recording medium, for directing the system to cascade (n+1) subqueries where each j-th subquery is a three-way join of the result of the last subquery, distinct j items from the candidate itemsets, and the transaction table; and
means, recorded on the recording medium, for directing the system to determine which of the (n+2)-itemsets are frequent using the results of the last subqueries.
30. The product as recited in claim 13, wherein the means for directing to generate rules includes:
means, recorded on the recording medium, for directing the system to put all items from the frequent itemsets into a table F;
means, recorded on the recording medium, for directing the system to generate a set of candidate rules from the table F using a table function;
means, recorded on the recording medium, for directing the system to join the candidate rules with the table F; and
means, recorded on the recording medium, for directing the system to filter out from the candidate rules those that do not meet a confidence criteria.
31. The product as recited in claim 13, wherein:
the query engine is an object-relational engine; and
the means for directing the system to generate 2-itemsets and (n+1)-itemsets include:
means, recorded on the recording medium, for directing the system to select from Vertical, GatherCount, and GatherJoin a method having the best cost for generating the (n+1)-itemsets;
if the Vertical method is selected, then means, recorded on the recording medium, for directing the system to transform the transaction table into a vertical format; and
means, recorded on the recording medium, for directing the system to generate the frequent (n+1)-itemsets using the selected method.
32. The product as recited in claim 31, wherein the cost for generating the itemsets is based on statistics about the data transactions and the candidate itemsets.
33. The product as recited in claim 13, wherein the query engine is an SQL engine.
Patent Citations (7)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US5615341 | 1997-03-01 | Agrawal et al. | Applicant |
| US5664171 | 1997-09-01 | Agrawal et al. | Applicant |
| US5664174 | 1997-09-01 | Agrawal et al. | Applicant |
| US5724573 | 1998-03-01 | Agrawal et al. | Applicant |
| US5832482 | 1998-11-01 | Yu et al. | Examiner |
| US5970464 | 1999-10-01 | Apte et al. | Examiner |
| US6094645 | 2000-07-01 | Aggarwal et al. | Examiner |
Non-Patent Literature (25)
- Tang et al., “Using Incremental Pruning to Increase the Efficiency of Dynamic Itemset Counting for Mining Asssociation Rules”, ACM 1998.Applicant
- Srikant et al, “Mining Quantitative Association Rules in Large Relational Tables”, ACM 1996.Applicant
- Sarawagi et al, “Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications”, ACM 1998, pp. 343-354.Applicant
- R. Agrawal et al., “Data Mining: A Performance Perspective,” IEEE Transactions on Knowledge and Data Engineering, vol. 5, No. 6, Dec. 1993, pp. 914-925.Applicant
- R. Agrawal et al., “Developing Tightly-Coupled Data Mining Applications on a Relational Database System,” Proceedings of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Oregon, Aug. 1996.Applicant
- R. Agrawal et al., “Fast Algorithms for Mining Association Rules,” Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994, pp. 487-499.Applicant
- R. Agrawal et al., “Mining Association Rules between Sets of Items in Large Databases,” Proceedings of the ACM-SIGMOD 1993 Int'l Conference on the Management of Data, Washington, DC, 1993, pp. 207-216.Applicant
- R. Agrawal et al., “Mining Sequential Patterns,” Proceedings of the Int'l Conference on Data Engineering, Taipei, Taiwan, 1995, pp. 3-14.Applicant
- Bayardo, Jr., “Brute-Force Mining of High-Conference Classification Rules,” Proceedings of the 3rd Int'l Conference on Knowlege Discovery and Data Mining, California, 1997.Applicant
- S. Brin et al., “Dynamic Itemset Counting and Implication Rules for Market Basket Data,” Proceedings of the ACM SIGMOD Conference on Management of Data, 1997.Applicant
- J. Han, “Discovery of Muliple-Level Association Rules from Large Databases,” Proceedings of the 21st VLBD Conference, Zurich, Switzerland, 1995, pp. 420-431.Applicant
- M. Houtsma, “Set-Oriented Mining for Assocation Rules in Relational Databases,” Proc. of the Int'l Conference on Data Engineering, Taipei, Taiwan, 1995, pp. 25-33.Applicant
- T. Imielinski et al., “A Database Perspective on Knowledge Discovery,” Communication of the ACM, vol. 39, No. 11, Nov. 1996, pp. 58-64.Applicant
- D. Lin et al., “Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set,” EDBT '98, Jun., 1998.Applicant
- H. Mannila et al., “Improved Methods for Finding Association Rules,” Pub. No. C-1993-65, University of Helsinki, 1993, pp. 1-20.Applicant
- R. Meo et al., “A New SQL-like Operator for Mining Association Rules,” Proceedings of the 22nd VLDB Conference Mumbai (Bombay), India, 1996.Applicant
- J.S. Park et al., “An Effective Hash-Based Algorithm for Mining Association Rules,” Proceedings of the 1995 ACM SIGMOD Conference, San Jose, California, 1995, pp. 175-186.Applicant
- J.S. Park et al., “Efficient Parallel Data Mining for Association Rules,” IBM Research Report, RJ20156, Aug., 1995, 26 pages.Applicant
- S. Sarawagi et al., “Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications,” IBM Research Report, RJ10107, Mar., 1998, 31 pages.Applicant
- A. Savasere et al., “An Efficient Algorithm for Mining Association Rules in Large Databases,” Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1995, pp. 432-444.Applicant
- A. Siebes et al., “KESO: Minimizing Database Interaction,” Proceedings of the 3rd Int'l Conference on Knowledge Discovery and Data Mining, California, 1997, pp. 247-250.Applicant
- R. Srikant et al., “Mining Association Rules with Item Constraints,” Proceedings of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Oregon, 1996, pp. 67-73.Applicant
- R. Srikant et al., “Mining Sequential Patterns: Generalizations and Performance Improvements,” IBM Research Report, RJ9994, Dec. 1995. Also in Proceedings of the 5th Conference on Extending Database Technology (EDBT) Avignon, France, 1996.Applicant
- M.J. Zaki et al., “New Algorithms for Fast Discovery of Association Rules,” Proceedings of the 3rd Int'l Conference on Knowledge Discovery and Data Mining, California, Aug. 1997, pp. 283-286.Applicant
- “Advances in Knowledge Discovery and Data Mining,” edited by U. M. Fayyad et al., AAAI Press / The MIT Press, Copyright 1996.Applicant