See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/228913454

An Implementation of the FP-growth Algorithm

Article · January 2010

DOI: 10.1145/1133905.1133907

CITATIONS READS
238 7,143

1 author:

Christian Borgelt
Paris Lodron University of Salzburg
385 PUBLICATIONS 5,509 CITATIONS

SEE PROFILE

All content following this page was uploaded by Christian Borgelt on 03 June 2014.

The user has requested enhancement of the downloaded file.

 An Implementation of the FP-growth Algorithm

Christian Borgelt
Department of Knowledge Processing and Language Engineering
School of Computer Science, Otto-von-Guericke-University of Magdeburg
Universitätsplatz 2, 39106 Magdeburg, Germany
borgelt@iws.cs.uni-magdeburg.de

ABSTRACT transaction database is preprocessed in a way that is com-

The FP-growth algorithm is currently one of the fastest ap- mon to basically all frequent item set mining algorithms.
proaches to frequent item set mining. In this paper I de- Section 3 explains how the initial FP-tree is built from the
scribe a C implementation of this algorithm, which contains (preprocessed) transaction database, yielding the starting
two variants of the core operation of computing a projec- point of the algorithm. The main step is described in Sec-
tion of an FP-tree (the fundamental data structure of the tion 4, namely how an FP-tree is projected in order to obtain
FP-growth algorithm). In addition, projected FP-trees are an FP-tree of the (sub-)database containing the transactions
(optionally) pruned by removing items that have become in- with a specific item (though with this item removed). The
frequent due to the projection (an approach that has been projection step is the most costly in the algorithm and thus
called FP-Bonsai). I report experimental results comparing it is important to find an efficient way of executing it. Sec-
this implementation of the FP-growth algorithm with three tion 5 considers how a projected FP-tree may be further
other frequent item set mining algorithms I implemented pruned using a technique that has been called FP-Bonsai
(Apriori, Eclat, and Relim). [4]. Such pruning can sometimes shrink the FP-tree con-
siderably and thus lead to much faster projections. Finally,
1. INTRODUCTION in Section 6 I report experiments with my implementation,
One of the currently fastest and most popular algorithms for comparing it with my implementations [5, 6] of the Apriori
frequent item set mining is the FP-growth algorithm [8]. It is [1, 2] and Eclat [10] algorithms.
based on a prefix tree representation of the given database
of transactions (called an FP-tree), which can save consid-
erable amounts of memory for storing the transactions. The
2. PREPROCESSING
Similar to several other algorithms for frequent item set min-
basic idea of the FP-growth algorithm can be described as a
ing, like, for example, Apriori or Eclat, FP-growth prepro-
recursive elimination scheme: in a preprocessing step delete
cesses the transaction database as follows: in an initial scan
all items from the transactions that are not frequent indi-
the frequencies of the items (support of single element item
vidually, i.e., do not appear in a user-specified minimum
sets) are determined. All infrequent items—that is, all items
number of transactions. Then select all transactions that
that appear in fewer transactions than a user-specified min-
contain the least frequent item (least frequent among those
imum number—are discarded from the transactions, since,
that are frequent) and delete this item from them. Recurse
obviously, they can never be part of a frequent item set.
to process the obtained reduced (also known as projected )
database, remembering that the item sets found in the recur-
In addition, the items in each transaction are sorted, so
sion share the deleted item as a prefix. On return, remove
that they are in descending order w.r.t. their frequency in
the processed item also from the database of all transactions
the database. Although the algorithm does not depend on
and start over, i.e., process the second frequent item etc. In
this specific order, experiments showed that it leads to much
these processing steps the prefix tree, which is enhanced by
shorter execution times than a random order. An ascending
links between the branches, is exploited to quickly find the
order leads to a particularly slow operation in my exper-
transactions containing a given item and also to remove this
iments, performing even worse than a random order. (In
item from the transactions after it has been processed.
this respect FP-growth behaves in exactly the opposite way
as Apriori, which in my implementation usually runs fastest
In this paper I describe an efficient C implementation of the
if items are sorted ascendingly, but in the same way as Eclat,
FP-growth algorithm. In Section 2 I briefly review how the
which also profits from items being sorted descendingly.)

This preprocessing is demonstrated in Table 1, which shows

Permission to make digital or hard copies of all or part of this work for an example transaction database on the left. The frequen-
personal or classroom use is granted without fee provided that copies are cies of the items in this database, sorted descendingly, are
not made or distributed for profit or commercial advantage and that copies
shown in the middle of this table. If we are given a user spec-
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific ified minimal support of 3 transactions, items f and g can
permission and/or a fee. be discarded. After doing so and sorting the items in each
OSDM’05, August 21, 2005, Chicago, Illinois, USA. transaction descendingly w.r.t. their frequencies we obtain
Copyright 2005 ACM 1-59593-210-0/05/08 ...$5.00. the reduced database shown in Table 1 on the right.

1
 a d f d a Of course, this is not the only way in which the initial FP-
a c de d 8 d c ae tree can be built. At first sight it may seem to be more
b d b 7 d b natural to build it by inserting transaction after transaction
b c d c 5 d b c into an initially empty FP-tree, creating the necessary nodes
b c a 4 b c for each new transaction. Indeed, such an approach even
a b d e 3 d b a has the advantage that the transaction database need not
b d e f 2 d b e be loaded in a simple form (for instance, as a list of integer
b c e g g 1 b c e arrays) into main memory. Since only one transaction is
c d f d c processed at a time, only the FP-tree representation and
a b d d b a one new transaction is in main memory. This usually saves
space, because an FP-tree is often a much more compact
Table 1: Transaction database (left), item frequen- representation of a transaction database.
cies (middle), and reduced transaction database
with items in transactions sorted descendingly w.r.t. Nevertheless I decided against such a representation for the
their frequency (right). following reasons: in order to build a prefix tree by sequen-
tially adding transactions, one needs pointers from parent
nodes to child nodes, so that one can descend in the tree
d: 8 d: 8 according to the items present in the transaction. However,
this is highly disadvantageous. As we will see later on, the
b: 7 b: 5 b: 2 further processing of an FP-tree, especially the main oper-
ation of projecting it, does not need such parent-to-child
c: 5 c: 1 c: 2 c: 2 pointers in my implementation, but rather child-to-parent
pointers. Since each node in an FP-tree (with the exception
a: 4 a: 2 a: 1 a: 1
of the roots) has exactly one parent, this, in principle, makes
it possible to work with nodes of constant size. If, however,
e: 3 e: 1 e: 1 e: 1
we have to accomodate an array of child pointers per node,
the nodes either have variable size or are unnecessarily large
Figure 1: FP-tree for the (reduced) transaction (because we have pointers that are not needed), rendering
database shown in Table 1. the memory management much less efficient.

It has to be conceded, though, that instead of using an array

3. BUILDING THE INITIAL FP-TREE of child pointers, one may also link all children into a list.
This, however, has the severe disadvantage that when in-
After all individually infrequent items have been deleted
serting transactions into the FP-tree, one such list has to be
from the transaction database, it is turned into an FP-tree.
searched (linearly!) for each item of the transaction in order
An FP-tree is basically a prefix tree for the transactions.
to find the child to go to—a possibly fairly costly operation.
That is, each path represents a set of transactions that share
the same prefix, each node corresponds to one item. In ad-
In contrast to this, first loading the transaction database
dition, all nodes referring to the same item are linked to-
as a simple list of integer arrays, sorting it, and building
gether in a list, so that all transactions containing a specific
the FP-tree with a recursive function (as outlined above),
item can easily be found and counted by traversing this list.
makes it possible to do without parent-to-child pointers en-
The list can be accessed through a head element, which also
tirely. Since the FP-tree is built top down, the parent is
states the total number of occurrences of the item in the
already known when the children are created. Thus it can
database. As an example, Figure 1 shows the FP-tree for
be passed down in the recursion, where the parent pointers
the (reduced) database shown in Table 1 on the right. The
of the children are set directly. As a consequence, the nodes
head elements of the item lists are shown to the left of the
of the FP-tree can be kept very small. In my implementa-
vertical grey bar, the prefix tree to the right of it.
tion, an FP-tree node contains only fields for (1) an item
identifier, (2) a counter, (3) a pointer to the parent node,
In my implementation the initial FP-tree is built from a
(4) a pointer to the successor node (referring to the same
main memory representation of the (preprocessed) transac-
item) and (5) an auxiliary pointer that is used when pro-
tion database as a simple list of integer arrays. This list
jecting the FP-tree (see below). That is, an FP-tree node
is sorted lexicographically (thus respecting the order of the
needs only 20 bytes (on a 32 bit machine).
items in the transactions, which reflects their frequency).
The sorted list can easily be turned into an FP-tree with a
However, if we used the standard memory management, al-
straightforward recursive procedure: at recursion depth k,
locating a block of memory for each node, there would be
the k-th item in each transaction is used to split the database
an additional overhead of 4 to 12 bytes (depending on the
into sections, one for each item. For each section a node of
memory system implementation) for each node for book-
the FP-tree is created and labeled with the item correspond-
keeping purposes (for instance, for storing the size of the
ing to the section. Each section is then processed recursively,
memory block). In addition, allocating and deallocating a
split into subsections, a new layer of nodes (one per subsec-
large number of such small memory blocks is usually not
tion) is created etc. Note that in doing so one has to take
very efficient. Therefore I use a specialized memory man-
care that transactions that are only as long as the current
agement in my implementation, which makes it possible to
recursion depth are handled appropriately, that is, are re-
efficiently handle large numbers of equally sized small mem-
moved from the section before going into recursion.

2
ory objects. The idea is to allocate larger arrays (with sev- d: 8 d: 8 d: 2
eral thousand elements) of these objects and to organize the
elements into a “free” list (i.e., a list of available memory b: 7 b: 5 b: 2
blocks of equal size). With such a system allocating and b: 1 b: 1
deallocating FP-tree nodes gets very efficient: the former c: 5 c: 1 c: 2 c: 2
c: 1 c: 1
retrieves (and removes) the first element of the free list, the
a: 4 a: 2 a: 1 a: 1
latter adds the node to deallocate at the beginning of the a: 1
free list. As experiments showed, introducing this special-
e: 3 e: 1 e: 1 e: 1
ized memory management led to a considerable speed-up.

Figure 2: Computing a projection of the database

4. PROJECTING AN FP-TREE w.r.t. the item e by traversing the lowest level and
The core operation of the FP-growth algorithm is to com- following all paths to the root.
pute an FP-tree of a projected database, that is, a database
of the transactions containing a specific item, with this item
removed. This projected database is processed recursively, d: 2 d: 2
remembering that the frequent item sets found in the recur-
sion share the removed item as a prefix. Figure 3: Resulting pro-
b: 2 b: 1 b: 1
jected FP-tree after it
My implementation of the FP-growth algorithm contains c: 2 c: 1 c: 1 has been detached from
two different projection methods, both of which proceed by the original FP-tree.
copying certain nodes of the FP-tree that are identified by a: 1 a: 1
the deepest level of the FP-tree, thus producing a kind of
“shadow” of it. The copied nodes are then linked and de-
tached from the original FP-tree, yielding an FP-tree of the
projected database. Afterwards the deepest level of the orig- FP-tree is then processed recursively with the prefix e. Note,
inal FP-tree, which corresponds to the item on which the however, that in this FP-tree all items are infrequent (and
projection was based, is removed, and the next higher level thus all item sets containing item e and one other item are
is processed in the same way. The two projections methods infrequent). Hence in this example, no recursive process-
differ mainly in the order in which they traverse and copy ing would take place. This is, of course, due to the chosen
the nodes of the FP-tree (branchwise vs. levelwise). example database and the support threshold.

The first method is illustrated in Figure 2 for the example The second projection method also traverses, in an outer
FP-tree shown in Figure 1. The red arrows show the flow loop, the deepest level of the FP-tree. However, it does not
of the processing and the blue “shadow” FP-tree is the cre- follow the chain of parent pointers up the root, but only
ated projection. In an outer loop, the lowest level of the copies the parent of each node, not its higher ancestors. In
FP-tree, that is, the list of nodes corresponding to the pro- doing so, it also copies the parent pointers of the original FP-
jection item, is traversed. For each node of this list, the nodes, thus making it possible to find the ancestors in later
parent pointers are followed to traverse all ancestors up to steps. These later steps consist in traversing the levels of the
the root. Each encountered ancestor is copied and linked (partially constructed) “shadow” FP-tree (not the levels of
from its original (this is what the auxiliary pointer in each the original one!) from bottom to top. On each level the
node, which was mentioned above, is needed for). During parents of the copied nodes (which are nodes in the original
the copying, the parent pointers of the copies are set, the tree) are determined and copied, and the parent pointers of
copies are also organized into level lists, and a sum of the the copies are set. That is, instead of branch by branch, the
counter values in each node is computed in head elements FP-tree is rather constructed level by level (even though in
for these lists (these head elements are omitted in Figure 2). each step nodes on several levels may be created). The ad-
vantage of this method over the one described above is that
Note that the counters in the copied nodes are determined for branches that share a path close to the root, this common
only from the counters in the nodes on the deepest level, path has to be traversed only once with this method (as the
which are propagated upwards, so that each node receives counters for all branches are summed before they are passed
the sum of its children. Note also that due to this we cannot to the next higher level). However, the experiments reported
stop following the chain of ancestors at a node that has below show that the first method is superior in practice. As
already been copied, even though it is clear that in this it seems, the additional effort needed for temporarily setting
case all ancestors higher up in the FP-tree must already another parent etc. more than outweighs the advantage of
have been copied. The reason is that one has to update the the better combination of the counter values.
number of transactions in the copies, adding the counter
value from the current branch to all copies of the ancestors 5. PRUNING A PROJECTED FP-TREE
on the path to the root. This is what the second projection After we obtained an FP-tree of a projected database, we
method tries to improve upon. may carry out an additional pruning step in order to sim-
plify the tree, thus speeding up projections. I got this idea
In a second traversal of the same branches, carried out in from [4], which introduces pruning techniques in a slightly
exactly the same manner, the copies are detached from their different context than pure frequent item set mining (suf-
originals (the auxiliary pointers are set to null), which yields fice it to say that there are additional constraints). One of
the independent projected FP-tree shown in Figure 3. This these techniques, however, can nevertheless be used here,

3
 a: 6 a: 6 a: 6 a: 6 log(time/s) over support

b: 1 b: 1 b: 1 1

c: 4 c: 1 c: 3 c: 4 c: 4

d: 3 d: 1 d: 2 d: 3 d: 3

Figure 4: α-pruning of a (projected) FP-tree.

0

log(time/s) over support 5 10 15 20 25 30 35 40 45 50 55 60

1 Figure 6: Results on T10I4D100K

0 log(time/s) over support

-1
34 35 36 37 38 39 40 41 42 43 44 45 1

Figure 5: Results on BMS-Webview-1

namely the so-called α-pruning. The idea of this pruning is 10 20 30 40 50 60 70 80 90 100

illustrated with a very simple example in Figure 4. Suppose
that the FP-tree shown on the left resulted from a projection Figure 7: Results on census
and that the minimum support is either 2 or 3. Then item b
is infrequent and is not needed in projections. However, it
gives rise to a branching in the tree. Hence, by removing it, log(time/s) over support
the tree can be simplified and actually turned into a simple
list, as it is shown on the right in Figure 4.
2
This pruning is achieved by traversing the levels of the FP-
tree from top to bottom. The processing starts at the level
1
following the first level that has a non-vanishing support
less than the minimum support. (Items having vanishing
support can be ignored, because they have no nodes in the 0
FP-tree.) This level and the following ones are traversed
and for each node the first ancestor with an item having
sufficient support is determined. The parent pointer is then 1200 1300 1400 1500 1600 1700 1800 1900 2000
updated to this ancestor, bypassing the nodes corresponding
to infrequent items. If by such an operation neighboring Figure 8: Results on chess
nodes receive the same parent, they are merged. They are
also merged, if their parents were different originally, but
have been merged in a preceding step. As an illustration
log(time/s) over support
consider the example Figure 4: after item b is removed,
the two nodes for item c can be merged. This has to be 2
recognized in order to merge the two nodes for item d also.

6. EXPERIMENTAL RESULTS 1

I ran experiments on the same five data sets that I already

used in [5, 6], namely BMS-Webview-1 [9], T10I4D100K [11], 0
census, chess, and mushroom [3]. However, I used a different
machine and an updated operating system, namely a Pen-
tium 4C 2.6GHz system with 1 GB of main memory running 200 300 400 500 600 700 800 900 1000
S.u.S.E. Linux 9.3 and gcc version 3.3.5). The results were
compared to experiments with my implementations of Apri- Figure 9: Results on mushroom
ori, Eclat, and Relim. All experiments were rerun to ensure
that the results are comparable.

4
Figures 5 to 9 show, each for one of the five data sets, the http://www.ics.uci.edu/˜mlearn/MLRepository.html
decimal logarithm of the execution time over different (ab-
solute) minimum support values. The solid black line refers [4] F. Bonchi and B. Goethals. FP-Bonsai: the Art of
to the implementation of the FP-growth algorithm described Growing and Pruning Small FP-trees. Proc. 8th
here, the dotted black line to the version that uses the al- Pacific-Asia Conference on Knowledge Discovery and
ternative projection method. The grey lines represent the Data Mining (PAKDD’04, Sydney, Australia),
corresponding results for Apriori (solid line), Eclat (dashed 155–160. Springer-Verlag, Heidelberg, Germany 2004
line), and Relim (dotted line).1 [5] C. Borgelt. Efficient Implementations of Apriori and
Eclat. Proc. 1st IEEE ICDM Workshop on Frequent
Among these implementations, all of which are highly opti- Item Set Mining Implementations (FIMI 2003,
mized, FP-growth clearly performs best. With the exception Melbourne, FL). CEUR Workshop Proceedings 90,
of the artificial dataset T10I4D100K, on which it is bet by Aachen, Germany 2003.
a considerable margin by Relim, and for higher support val- http://www.ceur-ws.org/Vol-90/
ues on BMS-Webview-1, where Relim also performs slightly
better (presumably, because it does not need to construct a [6] C. Borgelt. Recursion Pruning for the Apriori
prefix tree), FP-growth is the clear winner. Only on chess, Algorithm. Proc. 2nd IEEE ICDM Workshop on
Eclat can come sufficiently close to be called competitive. Frequent Item Set Mining Implementations (FIMI
2003, Brighton, United Kingdom). CEUR Workshop
The second projection methods for FP-trees (dotted black Proceedings 126, Aachen, Germany 2004.
line) generally fares worse, although there is not much dif- http://www.ceur-ws.org/Vol-126/
ference between the two methods on chess and mushroom.
This is a somewhat surprising result, because there are good [7] U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and
reasons to believe that the second projection method may be R. Uthurusamy, eds. Advances in Knowledge
able to yield better results than the first. I plan to examine Discovery and Data Mining. AAAI Press / MIT Press,
this issue in more detail in the future. Cambridge, CA, USA 1996
[8] J. Han, H. Pei, and Y. Yin. Mining Frequent Patterns
7. CONCLUSIONS without Candidate Generation. In: Proc. Conf. on the
In this paper I described an implementation of the FP- Management of Data (SIGMOD’00, Dallas, TX).
growth algorithm, which contains two methods for efficiently ACM Press, New York, NY, USA 2000
projecting an FP-tree—the core operation of the FP-growth
algorithm. As the experimental results show, this implemen- [9] R. Kohavi, C.E. Bradley, B. Frasca, L. Mason, and
tation clearly outperforms Apriori and Eclat, even in highly Z. Zheng. KDD-Cup 2000 Organizers’ Report: Peeling
optimized versions. However, the performance of the two the Onion. SIGKDD Exploration 2(2):86–93. 2000.
projection methods, especially, why the second is sometimes
[10] M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li.
much slower than the first, needs further investigation.
New Algorithms for Fast Discovery of Association
Rules. Proc. 3rd Int. Conf. on Knowledge Discovery
8. PROGRAM and Data Mining (KDD’97), 283–296. AAAI Press,
The implementation of the FP-growth algorithm described Menlo Park, CA, USA 1997
in this paper (Windowstm and Linuxtm executables as well
as the source code, distributed under the LGPL) can be [11] Synthetic Data Generation Code for Associations and
downloaded free of charge at Sequential Patterns. Intelligent Information Systems,
IBM Almaden Research Center
http://fuzzy.cs.uni-magdeburg.de/˜borgelt/software.html http://www.almaden.ibm.com/
At this URL my implementations of Apriori, Eclat, and Re- software/quest/Resources/index.shtml
lim are also available as well as a graphical user interface
(written in Java) for finding association rules with Apriori.

9. REFERENCES
[1] R. Agrawal, T. Imielienski, and A. Swami. Mining
Association Rules between Sets of Items in Large
Databases. Proc. Conf. on Management of Data,
207–216. ACM Press, New York, NY, USA 1993
[2] A. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and
A. Verkamo. Fast Discovery of Association Rules. In:
[7], 307–328
[3] C.L. Blake and C.J. Merz. UCI Repository of Machine
Learning Databases. Dept. of Information and
Computer Science, University of California at Irvine,
CA, USA 1998
1
Relim is described in a sibling paper that has also been
submitted to this workshop.

View publication stats