We present a depth-first algorithm, PatriciaMine, that discovers all frequent itemsets in a dataset, for a given support threshold. The algorithm is main-memory based and employs a Patricia trie to represent the dataset, which is space efficient for both dense and sparse datasets, whereas alternative representations were adopted by previous algorithms for these two cases. A number of optimizations have been introduced in the implementation of the algorithm. The paper reports several experimental results on real and artificial datasets, which assess the effectiveness of the implementation and show the better performance attained by PatriciaMine with respect to other prominent algorithms.
In this work, we focus on the problem of finding all
frequent itemsets in a dataset D of transactions over a set of
items I, that is, all itemsets X ⊆ I contained in a
number of transactions greater than or equal to a certain given
threshold [
Several algorithms proposed in the literature to discover
all frequent itemsets follow a depth-first approach by
considering one item at a time and generating (recursively) all
frequent itemsets which contain that item, before
proceeding to the next item. A prominent member of this class of
algorithms is FP-Growth proposed in [
∗This research was supported in part by MIUR of Italy under project “ALINWEB: Algorithmics for Internet and the Web”.
Improved variants of FP-Growth appeared in the
literature, which avoid physical projections of the dataset
(TopDown FP-Growth [
In this paper, we present an algorithm, PatriciaMine,
which further improves upon the aforementioned
algorithms stemmed from FP-Growth. Our main contribution
is twofold:
• We use a compressed (Patricia) trie to store the dataset,
which provides a space-efficient representation for
both sparse and dense datasets, without resorting to
two alternative structures, namely array-based and
triebased, as was suggested in [
We coded PatriciaMine in C, and compared its
performance with that of a number of prominent algorithms,
whose source/object code was made available to us, on
several real and artificial datasets. The experiments provide
clear evidence of the higher performance of PatriciaMine
with respect to these other algorithms on both dense and
sparse datasets. It must be remarked that our focus is on
main-memory execution, in the sense PatriciaMine works
under the assumption that the employed representation of
the dataset fits in main memory. If this is not the case,
techniques such as those suggested in [
The rest of the paper is organized as follows. Section 2
introduces some notation and illustrates the datasets used
in the experiments. Section 3 presents the main iterative
strategy adopted by PatriciaMine, which can be regarded
as a reformulation (with some modifications) of the
recursive strategies adopted in [
Let I be a set of items, and D a set of transactions, where each transaction t ∈ D consists of a distinct identifier tid and a subset of items tset ⊆ I. For an itemset X ⊆ I, its support in D, denoted by suppD(X), is defined as the number of transactions t ∈ D such that X ⊆ tset. Given an absolute support threshold min sup, with 0 < min sup ≤ |D|, an itemset X ⊆ I is frequent w.r.t. D and min sup, if suppD(X) ≥ min sup. With a slight abuse of notation, we call an item i ∈ I frequent if {i} is frequent, and refer to suppD({i}) as the support of i1. We study the problem of determining the set of all frequent itemsets for given D and min sup, which we denote by F (D, min sup). For an itemset X ⊆ I, we denote by DX the subset of D projected on those transactions that contain X.
Let I0 = {i1, i2, . . .} ⊆ I denote the subset of frequent
items ordered by increasing support, and assume that the
items in each frequent itemset are ordered accordingly. As
observed in [
1When clear from the context, we will refer to frequent items or itemsets, omitting D and min sup.
A sample dataset and the corresponding FIST for min sup = 3 are shown in Figures 1 and 2. Notice that a different initial ordering of the items in I0 would produce a different FIST. Most of the algorithms that compute F (D, min sup) perform either a breadth-first or a depth-first exploration of some FIST. In particular, our algorithm performs a depth-first exploration of the FIST defined above.
The experiments reported in this paper have been
conducted on several real and artificially generated datasets,
frequently used in previous works. We briefly describe them
below and refer the reader to [
Pos: From Blue-Martini Software Inc., contains years worth of point-of-sale data form an electronics retailer. WebView1, WebView2: From Blue-Martini Software Inc., contain several months of clickstream data from ecommerce web sites.
Pumsb, Pumsb*: derived by [
Connect-4, Chess: are relative to the respective games. 1. Determine I0 and D0; 2. Create IL and link it to D0;
X ← ∅; h ← 0; ` ← 0; while (` < |IL|) do 3. if (IL[`].count < min sup) then ` ← ` + 1;
else 4. if ((h > 0) AND (IL[`].item = X[h − 1])) 5. then ` ← ` + 1; h ← h − 1;
else 6. X[h] ← IL[`].item; 7. h ← h + 1; 8. Generate itemset X; 9. for i ← ` − 1 downto 0 do make IL[i].ptr point to head of t-list(i, DX0 );
IL[i].count ← support of IL[i].item in DX0 ;
` ← 0;
IBM-Artificial: a class of artificial datasets obtained using
the generator developed in [
Datasets from Blue-Martini Software Inc. and (usually) the artificial ones are regarded as sparse, while the other ones as dense.
The main strategy adopted by PatriciaMine is described
by the pseudocode in Figure 3 and is based on a depth-first
exploration of the FIST, similar to the one employed by the
algorithms in [
A first scan of the dataset D is performed to determine the set I0 of frequent items, and a pruned instance D0 of the original dataset where non-frequent items and empty transactions are removed (Step 1). Then, an Item List (IL) vector is created (Step 2), where each entry IL[`] consists of three fields: IL[`].item, IL[`].count, and IL[`].ptr, which store, respectively, a distinct item of I0, its support and a pointer. The entries are sorted by decreasing value of the support field, hence the most frequent items are positioned to the top of the IL. The IL is linked to D0 as follows. For each entry IL[`], the pointer IL[`].ptr points to a list that threads together all occurrences of IL[`].item in D0. We call such a list the threaded list for IL[`].item with respect to D0, and denote it by t-list(`, D0). The initial IL for the sample dataset and the t-lists built on a natural representation of the dataset, are shown in Figure 4. (The actual data structure used to represent D0 will be discussed in the next section.)
Then, a depth-first exploration of the FIST is started visiting the children of each node by decreasing support order (i.e., left-to-right with respect to Figure 2). This exploration is performed by the while-loop in the pseudocode. A vector X and an integer h are used to store, respectively, the itemset associated with the last visited node of the FIST and its length (initially, X is empty and h = 0, meaning that the root has just been visited).
Let us consider the beginning of a generic iteration of the while-loop and let v be the last visited node of the FIST, associated with itemset X = (a1, a2, . . . , ah), where ah is the item labelling v, and, for j < h, aj is the item labelling the ancestor wj of v at distance h−j from it. For 1 ≤ j ≤ h, let `j be the IL index such that IL[`j ].item = aj , and note that `h < `h−1 < · · · < `1; also denote by Xj the prefix (a1, a2, . . . , aj ) of X , which is the itemset associated with wj (clearly, X = Xh).
The following invariant holds at the beginning of the iteration. Let `0 be an arbitrary index of the IL, and suppose that `j+1 < `0 ≤ `j , for some 0 ≤ j ≤ h, setting for convenience `0 = |IL| − 1 and `h+1 = −1. Then, IL[`0].count stores the support of item IL[`0].item in DX0j , and IL[`0].ptr points to t-list(`0, DX0j ), that threads together all occurrences of IL[`0].item in DX0j (we let X0 = ∅ and DX0 = D0).
0
During the current iteration and, possibly, a number of
subsequent iterations, the node u which is either the first
child of v, if any, or the first unvisited child of one of v’s
ancestors is identified (Steps 3÷5). If no such node is found
the algorithm terminates. It is easily seen that the item
labelling u is the first item IL[`].item found scanning the IL
from the top, such that IL[`].count ≥ min sup and ` 6= `j
for every 1 ≤ j ≤ h. If node u is found, its
corresponding itemset is generated (Steps 6÷8). (Note that if u is the
child of an ancestor w of v, we have that before Step 6 is
executed X[0 . . . h − 1] correctly stores the itemset
associated with w.) Then, the first ` entries of the IL are updated
so to enforce the invariant for the next iteration (for-loop
of Step 9). Figure 5 shows the IL and t-lists for the
sample dataset at the end of the while-loop iteration where node
u=(L,4) is visited and itemset X = (L) is generated.
Observe that while the entries for items G and H (respectively,
IL[
0 .
The correctness of the whole strategy is easily established by noting that the invariant stated before holds with h = 0 at the beginning of the while-loop, i.e., at the end of the visit of the root of the FIST. 4. Representing the dataset as a Patricia trie
Crucial to the efficiency of the main strategy presented
in the previous section is the choice of the data structure
employed to represent the dataset D0. Some previous works
represented the dataset D0 through a standard trie, called
FP-tree, built on the set of transactions, with items sorted
by decreasing support [
For these reasons, it has been suggested in [
To avoid the need for two alternative data structures to
attain space efficiency, our algorithm resorts to a compressed
trie, better known as Patricia trie [
The standard and Patricia tries for the sample dataset are compared in Figure 6 and 7, respectively. As the figure shows, a Patricia trie may still retain some single-child nodes, however these nodes identify boundaries of transactions that are prefixes of other transactions. The following theorem provides an upper bound on the overall size of the
Theorem 1 A dataset D0 consisting of M transactions with aggregate size N can be represented through a Patricia trie of size at most N + O (M ).
Proof. Consider the Patricia trie described before. The trie has less than 2M nodes since each node which has either zero or one child accounts for (one or more) distinct transactions, and, by standard properties of trees, all other nodes are at most one less than the number of leaves. The theorem follows by noting that the total number of items stored at the nodes is at most N .
It is important to remark that even for sparse datasets, which exhibit a moderate sharing of prefixes among transactions, the total number of items stored in the trie may turn out much less than N , and if the number of transactions is M N , as is often the case, the Patricia trie becomes very space efficient. To provide empirical evidence of this fact, Table 1 compares the space requirements of the representations based on arrays, standard trie, and Patricia trie, for the datasets introduced before, on some fixed support thresholds. For each dataset the table reports: the number of transactions, the average transaction size (AvTS), the chosen support threshold (in percentage), and the sizes in bytes of the various representations (data are relative to datasets pruned of non-frequent items). An item is assumed to fit in one word (4 bytes). For the array-based representation we considered an overhead of 1 word for each transaction, while for the standard and Patricia tries, we considered an overhead per node of 4 and 5 words, respectively, which are needed to store the count, the pointer to the father and other information used by our algorithm (the extra word in each Patricia trie node is used to store the number of items at the node).
The data reported in the table show the substantial compression achieved by the Patricia trie with respect to the standard trie, especially in the case of sparse datasets. Also, the space required by the Patricia trie is comparable to, and often much less than that of the simple array-based representation. In the few cases where the former is larger, indicated in bold in the table, the difference between the two is rather small (and can be further reduced through a more compact representation of the Patricia trie nodes). Furthermore, it must be observed that in the execution of the algorithm additional space is required to store the threaded lists connected to the IL. Initially, this space is proportional to the overall number of items appearing in the dataset representation, which is smaller for the Patricia trie due to the sharing of prefixes among transactions.
Construction of the Patricia trie Although the Patricia trie provides a space efficient data structure for representing D0, its actual construction may be rather costly, thus influencing the overall performance of the algorithm especially if, as it will be discussed later, the dataset is projected a number of times during the course of the algorithm.
A natural construction strategy starts from an initial
empty trie and inserts one transaction at a time into it. To
insert a transaction t, the current trie is traversed downwards
along the path that corresponds to the prefix shared by t with
previously inserted transactions, suitably updating the count
at each node, until either t is entirely covered, or a point in
t is reached where the shared prefix ends. In the latter case,
the remaining suffix is stored into a new node added as a
child of the last node visited. In order to efficiently search
the correct child of a node v during the downward
traversal of the trie, we employ a hash table whose buckets store
pointers to the children of v based on the first items they
contain. (A similar idea was employed by the Apriori
algorithm [
A number of optimizations have been introduced and tested in the implementation of the main strategy described in Section 3. In the following subsections, we will always make reference to a generic iteration of the while-loop of Figure 3 where a new frequent itemset X is generated in Step 8 after adding, in Step 6, item IL[`].item. Also, we define as locally frequent items those items IL[j].item, with j < `, such that their support in DX0 is at least min sup.
After frequent itemset X has been generated, the discovery of all frequent supersets Y ⊃ X could proceed either on a physical projection of the dataset (i.e., a materialization of DX0 ) and on a new IL, both restricted to the locally frequent items, or on the original dataset D0, with DX0 is identified by means of the updated t-lists in the IL (in this case, a new IL or the original one can be used).
The first approach, which was followed in FP-Growth
[
In our implementation, we experimented several heuristics for limiting the number of projections. Although no heuristic was found superior to all others in every experiment, a rather simple heuristic exhibited very good performance in most cases: namely, to allow for physical projection only at the top s levels of the FIST and when the locally frequent items are at least k (in the experiments, s = 3 and k = 10 seemed to work fairly well). The rationale behind this heuristic is that the cost of projection is justified if the mining of the projected dataset goes on for long enough to take full advantage of the compression it achieves. Moreover, the heuristic limits the memory blowup by requiring at most s projected datasets to coexist in memory. Experimental results regarding the effectiveness of the heuristic, will be presented and discussed in Section 6.1 5.2. Immediate generation of subtrees of the FIST
Suppose that at the end of the for-loop every locally frequent item IL[j].item, with j < `, has support IL[j].count = IL[`].count = c in DX
0 . Let Z denote the set of the locally frequent items. Then, for every Z0 ⊆ Z we have that X ∪Z0 is frequent with support c. Therefore, we can immediately generate all of these itemsets and set ` = ` + 1 rather than resetting ` = 0 after the for-loop.2 Viewed on the FIST, this is equivalent to generate all nodes in the subtree rooted at the node associated with X, without actually exploring such a subtree.
A similar optimization was incorporated in previous implementations, but limited to the case when the t-list(`, DX0 ), pointed by IL[`].ptr, consists of a single node. Our condition is more general and encompasses also cases when t-list(`, DX0 ) has more than one node.
Another important issue concerns the implementation of the for-loop (Step 9), which contributes a large fraction of the overall running time. By the invariant previously stated, we have that, before entering the for-loop, IL[`].ptr points to head of t-list(`, DX0 ), that is, it threads together all of the occurrences of IL[`].item in nodes of the trie corresponding to transactions in DX
0 . Moreover, the algorithm must ensure that the count of each such node is relative to DX0 and not to the entire dataset. Let TX denote the portion of the trie whose leaves are threaded together by t-list(`, DX0 ).
The for-loop determines t-list(j, DX0 ) for every 0 ≤ j < ` − 1, and updates IL[j].count to reflect the actual support of IL[j].item in DX
0 . To do so, one could simply take
each occurrence of IL[`].item threaded by t-list(`, DX
0 ) and
walk up the trie suitably updating the count of each node
encountered, and the count and t-list of each item stored
at the node. This is essentially, the strategy implemented
by Top Down FP-growth [
In our implementation, we adopted an alternative strategy that, rather than traversing each individual leaf-root path in TX , performs a global traversal from the leaves to the root guided by the entries of the IL which are being updated. In this fashion, each node in TX is traversed only once. We refer to this strategy as the item-guided traversal. Specifically, the item-guided traversal starts by walking through the nodes threaded together in t-list(`, DX0 ). For each such node v, the count and t-list of each item IL[j].item stored in v, with j < `, are updated, and v is inserted in t-list(j, DX0 ) marked as visited. Also, the count and t-list of the last item, say IL[j0].item, stored in v’s father u are updated and u is inserted in t-list(j0, DX 0 ) marked as unvisited. After all nodes in t-list(`, DX 0 ) have been dealt with, the largest index j < ` is found such that t-list(j, DX
0 ) contains some unvisited nodes (which can be conveniently positioned at the front of the list). Then, the item-guided traversal is iterated walking through the unvisited nodes in t-list(j, DX0 ). It terminates when no threaded list is found that contains unvisited nodes (i.e., the top of the IL is reached). The following theorem is easily proved. Theorem 2 The item-guided traversal correctly visits all nodes in TX . Moreover, each such node with k direct children is touched k times and fully traversed exactly once.
This section presents the results of several experiments
we performed on the datasets described in Section 2.1.
Specifically, in Subsection 6.1 we assess the effectiveness
of our implementation, while in Subsections 6.2 and 6.3 we
compare the performance of PatriciaMine with that of other
prominent algorithms. The experiments reported in the first
two subsections have been conducted on an IBM RS/6000
SP multiprocessor, using a single 375Mhz POWER3-II
processor, with 4GB main memory, and two 9.1 GB SCSI
disks under the AIX 4.3.3 operating system. On this
platform, running times as well as other relevant quantities
(e.g., cache and TLB hits/misses) have been measured with
hardware counters, accessed through the HPM performance
monitor by [
A first set of experiments was run to verify whether allowing for physical projections of the dataset improves performance and if the heuristic we implemented to decide when to physically project the dataset is effective. The results of the experiments are reported in Figures 8 and 9 (running times do not include the output of the frequent itemsets). For each dataset, we compared the performance of PatriciaMine using the heuristic (line “WithProjection”) with the performance of a version of PatriciaMine where physical projection is inhibited (line “WithoutProjection”), on four different values of support, indicated in percentage. It is seen that the heuristic yields performance improvements, often very substantial, at low support values (e.g., see Connect4, Pumsb*, WebView1/2, T30.I16.D400k.N1k.L2k, and T40.I10.D100k.N1k.L2k) while it has often no effect or incurs a slight slowdown at higher supports. This can be explained by the fact that at high supports the FIST is shallow and the projection overhead cannot be easily hidden by the subsequent computation. Note that the case of Pos is anomalous. For this dataset the heuristic, and in fact all of the heuristics we tested, slowed down the execution, hence suggesting that physical projection is never beneficial. This case, however, will be further investigated.
We also tested the speed-up achieved by immediately generating all supersets of a certain frequent itemset X when the locally frequent items have the same support as X. In particular, we observed that the novelty introduced in our implementation, that is considering also those cases when the threading list t-list(`, DX 0 ) consists of more than one node, yielded a noticeable performance improvement (e.g., a factor 1.4 speed-up was achieved on WebView1 with support 0.054%, and a factor 1.6 speed-up was achieved on WebView2 with support 0.004%).
We finally compared the effectiveness of the implementation of the for-loop of Figure 3 based on the novel itemguided traversal, with respect to the straightforward one. Although the item-guided traversal is provably superior in an asymptotic worst-case sense (e.g., see Theorem 2 and the discussion in Section 5.3) , the experiments provided mixed results. For all dense datasets and for Pos, the item-guided traversal turned out faster than the straightforward one up to a factor 1.5 (e.g., for Mushroom with support 5%), while for sparse datasets it resulted actually slower by a factor at most 1.2. This can be partly explained by noting that if the tree to be traversed is skinny (as is probably the case for the sparse datasets, except for Pos) the item-guided traversal cannot provide a substantial improvement while it suffers a slight overhead for the scan of the IL. Moreover, for some sparse datasets, we observed that while the item-guided traversal performs a smaller number of instructions, it exhibits less locality (e.g., it incurs higher TLB misses) which causes the higher running time. We conjecture that a refined implementation could make the item-guided traversal competitive even for sparse datasets. WithProjection WithoutProjection
In this subsection, we compare PatriciaMine with other
prominent algorithms whose source code was made
available to us: namely FP-Growth [
DCI (Direct Count & Intersect) performs a breadth-first exploration of the FIST, generating a set of candidate itemsets for each level, computing their support, and then determining the frequent ones. It employs two alternative representations for the dataset, a horizontal and a vertical one, and, respectively, a count-based and intersection-based method to compute the supports, switching adaptively from one to the other based on the characteristics of the dataset.
Eclat, instead is based on a depth-first exploration
strategy (like FP-Growth and PatriciaMine). It employs a
vertical representation of the dataset which stores with each item
the list of transaction IDs (TID-list) where it occurs, and
determines an itemset’s support through TID-lists
intersections. The counting mechanism was successively improved
in dEclat [
For FP-Growth and Eclat, we used the source code developed by Goethals3, while for DCI we obtained the source code directly from the authors. The implementation of Eclat we employed includes the use of diffsets.
The experimental results are reported in Figures 10 and 11. For each dataset, a graph shows the running times achieved by the algorithms on four support values, indicated in percentages. (Here we included the output time since for DCI the writing on file of frequent itemsets is functional to the algorithm’s operation.) It is easily seen that the performance of PatriciaMine is significantly superior to that of Eclat and FP-Growth on all datasets and supports. We also observed that Eclat features higher locality than FP-Growth, exhibiting in some cases a better running time, though performing a larger number of instructions.
Compared to DCI, PatriciaMine is consistently and often substantially faster at low values of support, while at higher supports, where execution time is in the order of a few sec3Available at http://www.cs.helsinki.fi/u/goethals WebView1 0.075%Support0.067% T10I4D100k 0.060% Patricia DCI Eclat FP−growth onds, the two algorithms exhibit similar performance and sometimes PatriciaMine is slightly slower, probably due to the trie construction overhead. However, it must be remarked that small differences between DCI and Patricia at low execution times could also be due to the different format required of the initial dataset, and different input/output functions employed by the two algorithms.
Particularly relevant for our work is the comparison
between PatriciaMine and OpportuneProject [
Figures 12 and 13, report the performances exhibited by PatriciaMine and OpportuneProject on the Pentium/Windows platform for a number of datasets and supports. It can be seen that, the performance of Patrici2% 40% 0.01% Support0.005% 0.002% 2.5% Support0.5% 0.25% aMine is consistently superior, up to one order of magnitude (e.g., in Pumsb*). The only exception are Pos (see graph labelled “Pos with projection”) and the artificial dataset T30.I16.D400k.N1k.L2k. For Pos, we have already observed that our heuristic for limiting the number of physical projections does not improve the running time. In fact, it is interesting to note that by inhibiting projections, PatriciaMine becomes faster than OpportuneProject (see graph labelled “Pos without projection”). This suggests that a better heuristic could eliminate this anomalous case.
As for T30.I16.D400k.N1k.L2k, some measurements we performed revealed that the time taken by the initialization of the Patricia trie accounts for a significant fraction of the running time at high support thresholds, and such an initial overhead cannot be hidden by the subsequent mining activity. However, at lower support thresholds, where the computation of the frequent itemsets dominates over the trie construction, PatriciaMine becomes faster than OpportuneProject.
Finally we report that on WebView1 for absolute support 32 (about 0.054%), OpportuneProject ran out of memory while PatriciaMine successfully completed the execution. 10−1 0.075% Patricia Opportune Project 101 )( s e m i T 100 10500% 101 )( s e m i T 100 10−51% Patricia Opportune Project 2% Support 1%
Pumsb* 60% Support 50% 40% 10−1 0.065% 0.004%