Abstract:
A method for automatically generating associations of items included in a database. A user first specifies a support criteria indicating a strength of desired associations of items contained in the said database. Then, a recursive program is executed for generating a hierarchical tree structure comprising one or more levels of database itemsets, with each itemset representing item associations determined to have satisfied the specified support criteria. The recursive program includes steps of: characterizing nodes of the tree structure as being either active and enabling generation of new nodes at a new level of the tree, or inactive, at any given time; enabling traversal of the tree structure in a predetermined manner and projecting each of the transactions included in the database onto currently active nodes of the tree structure to generate projected transaction results; and, counting the projected transaction results of the projected transactions at the active nodes to determine whether the further itemsets satisfy the specified support criteria. All itemsets meeting the specified support criteria are added to the tree structure at a new level.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to the field of data mining, and more particularly, a novel data mining system and search methodology for generating associations among items in a large database. 
     2. Discussion of the Prior Art 
     The problem of finding association rules was introduced in a reference entitled “Mining Association Rules Between Sets of Items in Very Large Databases,” Proceedings of the ACM SIGMOD Conference on Management of Data, pages 207-216, 1993 authored by Agrawal R., Imielinski T., and Swami A. The problem identified in the reference was directed to finding the relationships between different items in a large database, e.g., a database containing customer transactions. Such information can be used for many sales purposes such as target marketing, because the buying patterns of consumers can be inferred from one another. 
     As described in the above-mentioned reference, there is first identified a set {I} comprising all items in the database of transactions. A transaction {T} which is a subset of {I} is defined to be a set of items which are bought together in one operation. An association rule between a set of items {X} which is a subset of {I} and another set {Y} which is also a subset of {I} is expressed as {X}=&gt;{Y}, and indicates that the presence of the items X in the transaction also indicates a strong possibility of the presence of the set of items Y. The measures used to indicate the strength of an association rule are support and confidence. The support of the rule X=&gt;Y is the fraction of the transactions containing both X and Y. The confidence of the rule X=&gt;Y is the fraction of the transactions containing X which also contain Y. In the association rule problem, it is desired to find all rules above a minimum level of support and confidence. The primary concept behind most association rule algorithms is a two phase procedure: In the first phase, all frequent itemsets (or large itemsets) are found. An itemset is “frequent” or large if it satisfies a user-defined minimum support requirement. The second phase uses these frequent itemsets in order to generate all the rules which satisfy the user specified minimum confidence. 
     Since its initial formulation, considerable research effort has been devoted to the association rule problem. A number of algorithms for large itemset generation have been proposed, such as those found in Agrawal R., Mannila H., Srikant R., Toivonen H., and Verkamo A. I. “Fast Discovery of Association Rules.” Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, Chapter 12, pages 307-328. Proceedings of the 20th International Conference on Very Large Data Bases, pages 478-499, 1994. and Brin S., Motwani R. Ullman J. D. and Tsur S., “Dynamic Itemset Counting and Implication Rules for Market Basket Data.” Proceedings of the ACM SIGMOD, 1997. pages 255-264. Variations of association rules such as generalized association rules, quantitative association rules and multilevel association rules have been studied in Srikant R., and Agrawal R., “Mining Generalized Association Rules.” Proceedings of the 21st International Conference on Very Large Data Bases, 1995, pages 407-419, and, Srikant R., and Agrawal R. “Mining Quantitative Association Rules in Large Relational Tables,” Proceedings of the ACM SIGMOD Conference on Management of Data, 1996, pages 1-12. 
     Although there are many previously proposed methods and systems, there is no efficient method which can generate large itemsets for very large scale problems. For these problems, current techniques require too much time to be of any practical use. The importance of solving such large scale problems is quite great, given the fact that most databases containing customer transaction data are quite large. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to a system and method for generating large database itemsets for very large scale problems. The system particularly employs the use of a lexicographic tree structural representation of large itemsets in the database that is particularly adapted for handling large scale problems. 
     According to the principles of the invention there is provided a system and method for automatically generating associations of items included in a database. A user first specifies a support criteria indicating a strength of desired associations of items contained in the said database. Then, a recursive or non-recursive program is executed for generating a hierarchical tree structure comprising one or more levels of database itemsets, with each itemset representing item associations determined to have satisfied the specified support criteria. The recursive program includes steps of characterizing nodes of the tree structure as being either active and enabling generation of new nodes at a new level of the tree, or inactive, at any given time; enabling traversal of the tree structure in a predetermined manner and projecting each of the transactions included in the database onto currently active nodes of the tree structure to generate projected transaction sets; and counting the support of the candidate extensions of nodes to determine whether the further itemsets satisfy the specified support criteria. All itemsets meeting the specified support criteria are added to the tree structure at a new level. 
     Advantageously, by projecting transactions upon the lexicographic tree structure, the CPU time for counting large itemsets is substantially reduced. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Further features and advantages of the invention will become more readily apparent from a consideration of the following detailed description set forth with reference to the accompanying drawings, which specify and show preferred embodiments of the invention, wherein like elements are designated by identical references throughout the drawings; and in which: 
     FIG. 1 is a diagram depicting a lexicographic tree graph structure which is used to count the itemsets of a large database; 
     FIG. 2 is a general description of the user interface provided for using the system of the invention; 
     FIG. 3 is a high-level flow diagram depicting the breadth-first creation of the lexicographic tree implemented in the methodology of the invention; 
     FIG. 4 is a more detailed flow diagram illustrating the counting step  320  of FIG. 3; 
     FIG.  5 ( a ) is a flow diagram describing the process of pruning inactive nodes from the lexicographic tree, and FIG.  5 ( b ) is an example pseudo-code depiction of the pruning tree process; 
     FIG.  6 ( a ) is a flow diagram describing a non-recursive “depth-first” process of projecting a block of transactions down the different nodes in the lexicographic tree for counting; 
     FIG.  6 ( b ) is a flow chart depicting the recursive “depth first” transaction projection strategy; and 
     FIGS.  7 ( a ) and  7 ( b ) depict a flow diagram of the process of adding to the counts of the matrices maintained at each level using the projected transactions. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1 is an example of the lexicographic tree structure  10  representing items in a large database defined as existing in a lexicographic ordering. As shown in FIG. 1, the tree  10  includes: (1) A vertex corresponding to each large itemset with the root of the tree corresponding to the null itemset; and, (2) nodes I={i 1 , . . . , ik} representing a large itemset, where i 1 , i 2 , . . . , ik are listed in a lexicographic order. The parent of the node I is the itemset {i 1 , . . . i(k−1)}. Various levels are indicated in the lexicographic tree that correspond to the sizes of the corresponding itemsets. Thus, for the example lexicographic tree  10  in FIG. 1, levels 0-4 are indicated, with level 0 being the empty or “null” node. 
     Additionally defined is a “frequent lexicographic tree extension” or, “tree extension” of an itemset which comprises those items that contribute to the extension and forming an edge in the lexicographic tree  10 . In the example illustrated in FIG. 1, the frequent lexicographic extensions of node “a” are b, c, d, and f. For purposes of discussion, the set of frequent lexicographic tree extensions of a node “P” is denoted as E(P). Additionally defined is the immediate ancestor “Q” of the itemset P in the lexicographic tree. The set of “candidate branches” of a node P is defined to be those items in E(Q) which occur lexicographically after the node P. These are the possible frequent lexicographic extensions of P in a set denoted as R(P). 
     Thus, in view of FIG. 1, the following relationships are defined: E(P) is a subset of R(P), which is a subset of E(Q). The value of E(P) in FIG. 1, when P=ab is {c,d}. The value of R(P) for P=ab is {c, d, f}, and for P=af, R(P) is empty. 
     For purposes of discussion, a node “P” is said to be “generated” when for the first time its existence is discovered by virtue of an extension of its parent. A node is further said to have been “examined” when its frequent lexicographic tree extensions have been determined. Thus, the process of examination of a node P results in generation of further nodes, unless the set E(P) for that node is empty. Thus, a node can be examined only after it has been generated. 
     The present invention is a methodology that enables the construction of a lexicographic tree in top-down fashion by starting at the null node (FIG. 1) and successively generating nodes until all nodes have been generated and subsequently examined. At any point in the implementation of the method, a node in the lexicographic tree is defined to be inactive, if all descendants of that node have already been generated. This implies that the sub-tree rooted at that node can not be further extended. Otherwise, the node is said to be active. Thus, the event of a node being active or inactive is dependent on the current state of the method which is generating the nodes. A node which has just been generated is always born active, but it becomes inactive later when all its descendants have been determined. In the illustrative example shown in FIG. 1, assuming that all nodes up to and including level 2 have already been examined, i.e., all nodes up to and including level 3 have been generated, the set of active nodes include those nodes labeled: abc, acd, ab, ac, a, and null. Thus, even though there are 23 nodes corresponding to the Levels 0-3 which have been generated, only 6 of them are active. Note that unexamined nodes “abd” and “acf” are not marked as active since the set of candidate branches for these nodes is empty. 
     An active node is said to be a boundary node if it has been generated but not examined. In the illustrative example of FIG. 1, the active boundary node set is {abc, acd}. As can be seen from the complete tree structure in the example of FIG. 1, the subsequent examination of the node “abc” will not lead to any further extensions, while the examination of the node “acd” will lead to the node “acdf.” 
     The extension set E(P) is produced when P is first examined. As the methodology progresses, some of these frequent extensions are no longer active. The term AE(P) thus denotes the subset of E(P) which is currently active, and are referred to herein as “active extensions.” These active extensions represent the branches at a node P which are currently active. 
     Additionally referred to herein is the set of “active items,” F(P), at a node P that is recursively defined as follows: (1) If the node P is a boundary node, then F(P)=R(P). (2) If the node P is not a boundary node, then F(P) is the union of AE(P) with active items of all nodes included in AE(P). Clearly, F(P) is a subset of E(P) and is a set which reduces in size when more itemsets are generated, since fewer number of items form active extensions. For the example tree structure shown in FIG. 1, for the null node, the only active extension is a, and the set of active items is {a, b, c, d, f}. It may also be noted that AE(P) is a subset of F(P). For node a, its active extensions are {b, c}, and the set of active items is {b, c, d, f}. 
     The methodology for constructing a lexicographic tree structure representing associated items of a large database that meets minimum support requirements is now described in greater detail. 
     During the lexicographic tree construction methodology of the invention, the following information is stored at each node: (1) the itemset P at that node; (2) the set of lexicographic tree extensions at that node which are currently active, i.e., AE(P); and, (3) the set of active items F(P) at that node. F(P) and AE(P) are updated whenever the set of boundary nodes changes. 
     Let “P” be a node in the lexicographic tree corresponding to a frequent itemset. Then, for a transaction T, a projected transaction T(P) is defined as being equal to (T (intersection) F(P)) where “intersection” refers to the set intersection operation. However, if T does not contain the itemset corresponding to node P then T(P) is null. If T(P) has less than two items then also it is eliminated because a transaction T(P) with less than two items does not contain any information which is necessary to count itemsets which are descendants of the node P. Actually, for the transaction to be useful at a non-boundary node P, more items are needed in T(P). The exact number depends on the depth of boundary nodes from node P. For a set or block of transactions “Tau,” the projected transaction set Tau(P) is defined as the set of projected transactions in Tau with respect to active items F(P) at P. 
     For example, consider a transaction “abcdefghk” applied to the illustrative lexicographic tree  10  of FIG. 1, the projected transaction at node “null” would be {a, b, c, d, e, f, g, h, k} (intersection) {a, b, c, d, f}=abcdf. The projected transaction at node “a” would be bcdf. For the transaction abdefg, its projection on node ac is null because it does not contain the required itemset “ac.” 
     In the discussion of the preferred methodology of the invention, the following points are emphasized: (1) An inactive node does not provide any extra information which is useful for further processing and thus, can be eliminated from the lexicographic tree; and, (2) for a given transaction T, the information required to count the support of any itemset which is a descendant of a node P is completely contained in T(P). 
     FIG. 2 illustrates an example user-interface having entry fields  220  and  230  enabling users to specify values of minimum support and minimum confidence, respectively. In response to these entries, large itemsets and rules are generated in accordance with the method of the invention for display in screen display area  210 . Associated with each large itemset is a minimum support value, while associated with each rule is a minimum confidence value. A database  240  is additionally provided that is populated with records of all commercial transactions, e.g., customer retail purchases collected over a particular time period. Each transaction record includes: a transaction id, and a number of corresponding actual item ids, comprising as SKU codes, for example, pertaining to a customer&#39;s transaction or purchase. As will be described, the transactions from this database  240  are projected onto the active nodes of the tree  10  in the node examination process. 
     It should be understood that various strategies are feasible for lexicographic tree creation and is a design choice depending upon trade-offs in I/O, memory, and CPU performance. For instance, either all nodes at level k may be created before nodes at level (k+1), or longer patterns may be discovered earlier in order to remove some of the other branches of the tree. One such strategy implements a “breadth-first” search, where all nodes at level k are created before nodes at level (k+1). Another strategy implements a “depth-first” creation, with all frequent descendants of a given node determined before any other node. 
     In breadth-first creation, all nodes at level k are created before nodes at level (k+1). At any given level k, the information regarding the possible items which can form frequent lexicographic extensions of it can be obtained from its parent at level (k−1). A given item i may be a frequent lexicographic extension of a node only if it is also a frequent lexicographic extension of its immediate parent and occurs lexicographically after it. Thus, while finding (k+1)-itemsets, all possible frequent lexicographic extensions of each (k−1)-itemset are determined. For a given node at level (k−1), if there are m such extensions, then there are m(m−1)/2 possible (k+1)-itemsets which are descendants of this (k−1)-itemset. In order to count these m(m−1)/2 possible extensions, use is made of projected transaction sets which are stored at that node. The use of projected transaction sets in counting support is important in the reduction of the CPU time for counting large itemsets. 
     The overall process of a “breadth-first” search  300  in accordance with the invention is illustrated as shown in FIG.  3 . At steps  302  and  304 , the null node for the lexicographic tree is generated, as are all the nodes at level 1, which may be accomplished by evaluating the support of each item in the database. Thus, the first two levels of the tree are built. At step  306  a counter “k” denoting the last level of the tree which has so far been generated, is set to 1. At step  320 , matrices to the level -(k−1) nodes are created and the support of the candidate nodes at level (k+1) are counted. As will be described in greater detail, counting of support of nodes at level k+1 entails projecting transactions to the level k−1 node, and particularly, counting corresponding items of the projected transactions by incrementing corresponding entries in a triangular matrix maintained at that node. Thus, in first pass through the algorithm  300 , it is desired to generate new nodes at level k+1. To do this, a triangular matrix is first generated at the null node (K−1=0; K=1), comprising all of the possible candidate doubles (itemsets) which may be generated at level 2 (K=1, K+1=2). 
     Generally, the process of counting support of the (k+1)-itemsets is accomplished as follows: Letting P be any (k−1)-itemset whose frequent extensions E(P) (nodes at level k) have already been determined. At each such node P, a matrix of size |E(P)|*|E(P)| is maintained. A row and column exists in this matrix for each item “i” in E(P). As will be described in greater detail with respect to FIG. 4, the (i,j) th  entry of this matrix indicates the count of the itemset [P (union) {i, j}] where “union” refers to the set union operation. Since the matrix is symmetric, only the lower triangular part of the matrix is maintained. For the illustrative example of FIG. 1, the triangular matrix maintained at the null node for the k=1 iteration (finding nodes at k=2) is depicted as follows:          [                    ab                                                           ac       bc                                               ad       bd       cd                                   ae       be       ce       de                       af       bf       cf       df       ef         ]                               
     For each item pair {i, j} in the projected transaction T(P), the entry (i, j) in this matrix is incremented by one. As further shown in FIG. 3, at step  335 , a determination of the support of all the candidate nodes (k+1 level) in the lexicographic tree is made, and, new nodes at level (k+1) of the tree which have sufficient support, are generated. Particularly, once the process of counting is complete, the frequent (k+1)-itemsets which are descendants of P is determined by using those entries in the matrix which have support larger than the user-defined minimum support value, as indicated at step  335 , FIG.  3 . Then, as indicated at step  340 , the counter k is incremented by 1, and, at step  360 , all inactive nodes and list of active items from the tree are “pruned.” At step  370 , a determination is made as to whether the active item list at the node null is empty. If the active item list at node null is empty, the method terminates at step  380 , i.e., no more (k+1) level nodes can be generated. Otherwise, the process returns to step  320  of FIG. 3 where the counting of support for active nodes at the next active level (k+1) is made. As shown in FIG. 3, the process of generating large (k+1)-itemsets from k-itemsets is repeated for increasing k until the k th  level of the tree is null, i.e., all the nodes in the tree are inactive. 
     The hierarchical structure of the lexicographic tree is useful in creating a set of projected transactions for the (k−1)-itemsets. This is quite important in the reduction of CPU time for itemset counting, as will be described in greater detail. The transactions may be projected recursively down the tree in order to create all the projected sets up to the (k−1) th  level. This projected set is a small subset of the original transaction set for each node. However, the total space occupied by the projected transactions over all nodes may be much larger than the original database size. Thus, it may be necessary to read a block of transactions from the database into main memory, create the projected transactions up to the (k−1) th  level, and use these projected transactions to add to the counts of the matrices maintained at that level. 
     The process of counting the support of the matrices at the level (k−1) nodes (step  320 , FIG. 3) is now described in greater detail in view of FIG.  4 . As shown in FIG. 4, at step  410 , the transaction database and the lexicographic tree up to level (k−1) is input to the process illustrated in FIG.  4 . As shown at step  415 , triangular matrices at level (k−1) nodes are initialized. At step  420 , a block of transactions are read from the database  240  (FIG. 2) or disk, and each transaction in the block is projected to all nodes at level (k−1), as indicated at step  430 , and described in further detail herein with reference to FIGS.  6 ( a ) and  6 ( b ). Additionally, at step  430 , the counts of the matrices maintained at those (k−1) th  level nodes are incremented. Then, at step  450 , a check is made to determine if all transactions have been read, and if all transactions have been read, the process terminates at step  460 . Otherwise, if more transactions need to be read out of the database, the process steps  420 - 450  repeat until all of the transactions have been read. 
     The process of transaction projection and counting for each block, as indicated at step  430  of FIG. 4, is now described in greater detail in view of FIGS.  6 ( a ) and  6 ( b ). It is understood that several strategies may be implemented in projecting transactions to boundary nodes where eventual counting is done. These strategies include: a “breadth-first” order wherein all transactions in the database are projected to all nodes at a level k−1 in order to create the nodes at level k+1; a “depth-first” order strategy wherein all transactions in a block are projected in a depth first order. 
     When a block of transactions is simultaneously projected to all nodes at level −(k−1) in a breadth first order, the total amount of memory required for all projections is very large. The memory requirements may be reduced by doing the projections in a “depth-first” order. In this scheme, the projected transaction sets are maintained for all nodes (and their siblings) for the path from the root to the node [at level −(k−1)] which is currently being extended. 
     FIG.  6 ( a ) illustrates a non-recursive “depth-first” order strategy wherein transaction projection at boundary nodes is performed for all active nodes and extensions along a particular path. As shown at step  610 , FIG.  6 ( a ), an ordered “LIST” of nodes to be used in order to perform the tree exploration, is maintained, with the LIST set to be the root of the tree, i.e., the null node. As indicated at step  620 , the last node “X” on LIST is picked, and deleted from the LIST. At step  630 , all children of “X” are added to the end of LIST, such that the lexicographically least node comes last. With Tau being the set of transactions at node X, Tau is projected onto all children of node X, as indicated at step  640 . When a transaction set is projected onto a node at level (k−1), the counts of the matrices which are maintained at that level are added. Thus, it is necessary to update the counts for the matrices maintained at each sibling node incrementally, i.e., one by one. The details of how a set of projected transactions is used in order to add to the counts of the matrix at a level is hereinafter described in greater detail with respect to FIG.  7 . At step  650 , FIG.  6 ( a ), a check is then made to determine if the LIST is empty. If the LIST is empty, the process terminates at step  660 , since the set of transactions has been projected to all the nodes in the tree. Otherwise, the process returns to step  620 . It should be understood that the procedure in FIG.  6 ( a ) is optional and may not be necessary for counting large 1-itemsets. 
     In another embodiment, the process of transaction projection and counting may be performed recursively, such as depicted by the flow diagram shown in FIG.  6 ( b ). In FIG.  6 ( b ), transaction projection and counting is performed recursively down the lexicographic tree  10  in order to create all the projected transaction sets up to the level (k−1). Each projected set is a small subset of the original transaction set for each node. The method  670  of FIG.  6 ( b ) is a recursive implementation of step  430 , FIG. 4, which projects a block of transactions to all nodes at level (k−1) in depth-first order, and adds the counts of the matrices maintained at those nodes. As shown at step  671 , a determination is first made as to whether node N is at level (k−1). If node N is not at level (k−1), then a recursive do loop begins at step  673 . In the loop, at step  675 , transaction set Tau is projected onto the i th  extension of node N, now defined as Tau′ (i), and, at step  678 , the procedure calls itself recursively for extension I of node N and transaction set Tau′ (i). At step  680 , a determination is made as to whether the do loop is done, and if so, terminates at step  690 . When the node is at level (k−1), the process proceeds to step  685  where the counts are added to the triangular matrix at node N using the transaction set Tau. 
     The method of performing the projections in FIG.  6 ( b ) seems to indicate that the projection at a node occurs in pure depth-first order. However, in order to avoid multiple passes through the transaction set, the projections are performed to all the children of a given node at the same time. The embodiment of FIG.  6 ( a ) clearly shows this detail. Preferably, upon a determination that a projection is no longer needed, that projection is deleted, thus freeing up memory which can be utilized for the next set of projections. 
     As previously mentioned, step  360  of FIG. 3 provides for the pruning of all those nodes which have been determined to be inactive. That is, after all frequent level (k+1)-itemsets have been determined, the nodes which are inactive are pruned. Thus, in the next iteration, when level (k+2)-itemsets are being counted, the time for projecting transactions is greatly reduced as only active nodes are used in the projection. Thus, at any node P, as the algorithm progresses, the projected transaction set Tau(P) keeps shrinking both in terms of the number of transactions as well as the number of items in transactions. This is because the active itemset F(P) is also shrinking as the algorithm progresses. Thus, if a tree at level-k is being generated, then for a node P at level-m, the projection of a transaction T(P) must have at least (k-m) items for it to be useful to extend the tree at level-k. If it has fewer items, it is eliminated. 
     The process of pruning the nodes of the tree is illustrated in FIG.  5 ( a ). At step  500 , the current level k of the tree which has just been generated is first input. In step  503 , all inactive nodes at level −k are removed. In step  506 , the active item list at each level −k node is set to the set of candidate extensions at that node. At step  510 , an index i is set equal to k−1, which is the current level of the tree which was being extended. Using recursion, the inactive items are removed from the tree in bottom up fashion. Thus, as indicated at step  520 , any node at level i which has no active extensions, is removed. In step  525 , the active item lists of the nodes at level i are updated to the union of their active extensions along with their active item lists. In step  530 , i is decremented by one, and, at step  540 , a check is made to determine if i&gt;=0, i.e., if pruning has occurred for every level up to the null node. If pruning has not occurred for every level up to the null node, then the process returns to step  520  for further removal of nodes at the new level i; otherwise, the process terminates at step  550 . 
     The pseudo-code for pruning the lexicographic tree after (k+1) itemsets have been generated is illustrated in FIG.  5 ( b ). As illustrated in the pseudo-code, the tree is pruned in bottom-up fashion, whence the level (k+1) is pruned first, then the level k, and so on up to level k=0. At the same time, the active lists of the nodes are constructed for the different levels of the tree. 
     Referring now to FIG.  7 ( a ), there is illustrated the process of using a set of projected transactions in order to add to the counts of the matrices maintained at a given level. As indicated at step  700 , the block “Tau” of transactions is projected at a node Y having a corresponding matrix. At step  710 , the counter i is set to 1, and at step  720 , the i th  transaction “T” from the block Tau is selected. For each pair of items in T, one is added to the count of the corresponding entry in the matrix, as indicated at step  730 . A detailed description of how the transaction is used in order to add to the counts of the corresponding entries in the matrix is will be described in further detail in view of FIG.  7 ( b ). Referring back to FIG.  7 ( a ), at step  740 , a check is made to determine whether all transactions in the block have already been used for the counting. If all transactions in the block have already been used for the counting, the process is terminated at step  760 ; otherwise, the process proceeds to step  750  where the transaction count “i” is incremented. The process steps  720 - 750  then repeat until all transactions in the block Tau have been used for the counting. 
     FIG.  7 ( b ) illustrates the process of adding to the counts of the matrix maintained at a node by using a single transaction. For purposes of explanation, it is assumed that the counters for the item numbers in the transaction are j and k, i.e., j and k represent the position numbers of the items in the transaction when counting from the left. Thus, as indicated at step  780 , j is set to 1, and at step  790 , k is set to j+1. At step  800 , a value of 1 is added to the entry in the matrix corresponding to the j th  and k th  items in the transaction. At step  810 , the counter k is incremented by 1, and at step  820 , a determination is made as to whether the counter k has reached the end of the transaction. If the counter k has not reached the end of the transaction, i.e., k&lt;=number of items in T, then the next iteration is performed by returning to step  800 ; otherwise, the counter j is incremented by 1 as indicated at step  830 . Then, at step  840 , a check is made to determine whether j is less than the number of items in the transaction T, i.e., j&lt;number of items in T. If j is less than the number of items in the transaction T, then the process returns to step  790  to reset counter k according to the new value of j; otherwise, the process terminates at step  850 . 
     While the invention has been particularly shown and described with respect to illustrative and preformed embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention which should be limited only by the scope of the appended claims. For instance, those skilled in the art may infer that it is not necessary for the methodology of the present invention to always create the nodes of the tree in breadth-first order. It is possible to either create the nodes depth-first or, in any combination of depth-first and breadth-first which may optimize performance.