=Paper=
{{Paper
|id=Vol-2668/paper3
|storemode=property
|title=LCM is Well Implemented CbO: Study of LCM from FCA Point of View
|pdfUrl=https://ceur-ws.org/Vol-2668/paper3.pdf
|volume=Vol-2668
|authors=Radek Janostik,Jan Konecny,Petr Krajča
|dblpUrl=https://dblp.org/rec/conf/cla/Janostik0K20
}}
==LCM is Well Implemented CbO: Study of LCM from FCA Point of View==
https://ceur-ws.org/Vol-2668/paper3.pdf
LCM is well implemented CbO:
study of LCM from FCA point of view
Radek Janostik, Jan Konecny, and Petr Krajča
Dept. Computer Science, Palacký University Olomouc
17. listopadu 12, CZ–77146 Olomouc, Czech Republic
{radek.janostik, jan.konecny, petr.krajca}@upol.cz
Abstract. LCM is an algorithm for enumeration of frequent closed
itemsets in transaction databases. It is well known that when we ig-
nore the required frequency, the closed itemsets are exactly intents of
formal concepts in Formal Concept Analysis (FCA). We describe LCM
in terms of FCA and show that LCM is basically the Close-by-One al-
gorithm with multiple speed-up features for processing sparse data. We
analyze the speed-up features and compare them with those of similar
FCA algorithms, like FCbO and algorithms from the In-Close family.
Keywords: algorithm; formal concept analysis; frequent closed itemset;
close-by-one
1 Introduction
Frequent closed itemsets in transaction databases are exactly intents in Formal
Concept Analysis (FCA) with sufficient support—cardinality of the correspond-
ing extents. If the minimum required support is zero (i.e. any attribute set is
considered frequent), one can easily unify these two notions. LCM (Linear time
Closed itemset Miner) is an algorithm for the enumeration of frequent closed
itemsets developed by Takeaki Uno [15,16,17,18] in 2003–2005. It is considered
to be one of the most efficient algorithms for this task.1
We have thoroughly studied Uno’s papers and source codes and, in the
present paper, we deliver a complete description of LCM from the point of view
of FCA. Despite the source codes being among the main sources for this study,
we stay at a very comprehensible level in our description and avoid delving into
implementation details. We explain that the basis of LCM is Kuznetsov’s Close-
by-One (CbO) [11].2 We describe its additional speed-up features and compare
them with those of state-of-art CbO-based algorithms, like FCbO [14] and In-
Close2+ [4,5,6,7].3
1
Its implementations with source codes are available at URL http://research.nii.
ac.jp/~uno/codes.htm.
2
Although LCM was most likely developed independently.
3
In the rest of this paper, whenever we write ‘CbO-based algorithms’ we mean CbO,
FCbO and In-Close family of algorithms. By version number 2+, we mean the version
2 and higher.
Copyright c 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). Published in Francisco
J. Valverde-Albacete, Martin Trnecka (Eds.): Proceedings of the 15th International
Conference on Concept Lattices and Their Applications, CLA 2020, pp. 47–58, 2020.
48 Radek Janostik et al.
Remark 1 (Some subjective notes on our motivations). Besides the obvious im-
portance of LCM for FCA4 , there are two motivational points for this work. We
separated them into this remark as they are based on our subjective impressions
and views. We ask the reader to excuse the rather subjective tone in this remark.
(a) A significant part of the FCA community is aware of LCM and uses Uno’s
implementation to enumerate formal concepts for further processing or for
comparison with their methods. However, it is our impression that, more
often than not, the implementation is used merely as a black box. We believe
that this part of the FCA community would appreciate ‘unwrapping the
black box’.
(b) Uno’s papers provide quite confusing descriptions of LCM and the source
codes of the implementations are not written to allow easy analysis. More-
over, Uno’s implementation and description of LCM have some differences;
there is even an important feature present in the implementation which is
not described in the papers. We believe that a clearer and more complete
description would be fruitful.
The paper is structured as follows. First, we recall the basic notions and
notations of FCA (Section 2) we use in the rest of this paper. Then we describe
CbO (Section 3) as it is a basis for description of LCM. Afterwards, we provide
a description of LCM’s features (Section 4), namely, initial preprocessing of data
(Section 4.1), handling data using arraylists computing all attribute extents at
once (Section 4.2), conditional datasets (Section 4.3), and pruning (Section 4.4).
In all of the above, we ignore the requirement of frequency and we describe it
separately (Section 5). Finally, we summarize our conclusions (Section 6).
2 Formal Concept Analysis
An input to FCA is a triplet xX, Y, Iy, called a formal context, where X and Y are
non-empty sets of objects and attributes, respectively, and I is a binary relation
between X and Y ; xx, yy P I means that the object x has the attribute y. Finite
formal contexts are usually depicted as tables, in which rows represent objects,
columns represent attributes, and each entry contains a cross if the corresponding
object has the corresponding attribute, and is left blank otherwise. In this paper,
we consider only finite formal contexts.
The formal context induces concept-forming operators:
Ò
: 2X Ñ 2Y assigns to a set A of objects the set AÒ of all attributes shared
by all the objects in A.
Ó
: 2Y Ñ 2X assigns to a set B of attributes the set B Ó of all objects which
share all the attributes in B.
4
However, the closed sets are also relevant in other disciplines, like association rule
mining [1,8], condensed representation of inductive queries [13], or logical analysis
of data [2,3].
LCM is well implemented CbO: study of LCM from FCA point of view 49
Formally,
AÒ “ ty P Y | @x P A : xx, yy P Iu, and B Ó “ tx P X | @y P B : xx, yy P Iu.
For singletons, we use shortened notation and write xÒ , y Ó instead of txuÒ , tyuÓ ,
respectively.
In this paper, we assume a set of attributes Y “ t1, . . . , nu. Whenever we
write about lower and higher attributes, we refer to the natural ordering ď of
the numbers in Y .
A formal concept is a pair xA, By of sets A Ď X, B Ď Y , such that AÒ “ B
and B Ó “ A. The first component of a formal concept is called the extent, whilst
the second one is called the intent.
The compositions ÒÓ and ÓÒ of concept-forming operators are closure opera-
tors on 2X and 2Y , respectively. That is, the composition ÓÒ satisfies
(extensivity) B Ď B ÓÒ (1)
ÓÒ ÓÒ
(monotony) B Ď D implies B ĎD (2)
ÓÒ ÓÒÓÒ
(idempotency) B “B (3)
for all B, D Ď Y (analogously for the composition ÒÓ ).
Sets of attributes satisfying B “ B ÓÒ are called closed sets and they are
exactly the intents of formal concepts.
3 Close-by-One
In the context of FCA, the foundation of LCM is CbO.5 Therefore, we firstly
turn our attention to CbO.
We start the description of CbO with a naı̈ve algorithm for generating all
closed sets. The naı̈ve algorithm traverses the space of all subsets of Y , each
subset is checked for closedness and is outputted. This approach is quite ineffi-
cient as the number of closed subsets is typically significantly smaller than the
number of all subsets.
The algorithm is given by a recursive procedure GenerateFrom, which accepts
two attributes:
‚ B – the set of attributes, from which new sets will be generated.
‚ y – the auxiliary argument to remember the highest attribute in B.
The procedure first checks the input set B for closedness and prints it if it is
closed (lines 1,2). Then, for each attribute i higher than y:
5
It is called a backtracking algorithm with prefix-preserving closure extensions in
Uno’s papers.
50 Radek Janostik et al.
Algorithm 1: Naı̈ve algorithm to enumerate closed subsets
def GenerateFrom(B, y):
input : B – set of attributes
y – last added attribute
1 if B “ B ÓÒ then
2 print(B)
3 for i P ty ` 1, . . . , nu do
4 D Ð B Y tiu
5 GenerateFrom(D, i)
6 return
GenerateFrom(H, 0)
‚ a new set is generated by adding the attribute i into the set B (line 4);
‚ the procedure recursively calls itself to process the new set (line 5).
The procedure is initially called with an empty set and zero as its arguments.
The naı̈ve algorithm represents a depth-first sweep through the tree of all
subsets of Y (see Fig. 1) and printing the closed ones.
1
H
2 10 14 16
1 2 3 4
3 7 9 11 13 15
2 3 4 3 4 4
4 6 8 12
3 4 4 4
5
4
Fig. 1. Tree of all subsets of t1, 2, 3, 4u. Each node represents a unique set containing all
elements in the path from the node to the root. The dotted arrows and small numbers
represent the order of traversal performed by the algorithm for generating all subsets.
In the tree of all subsets (Fig. 1), each node is a superset of its predecessors.
We can use the closure operator ÓÒ to skip non-closed sets. In other words, to
make jumps in the tree to closed sets only. Instead of simply adding an element
to generate a new subset D Ð B Y tiu, CbO adds the element and then closes
the set
D Ð pB Y tiuqÓÒ . (4)
We need to distinguish the two outcomes of the closure (4). Either
– the closure contains some attributes lower than i which are not included in
B, i.e. Di ‰ Bi where Di “ D X t1, . . . , i ´ 1u, Bi “ B X t1, . . . , i ´ 1u;
– or it does not, and we have Di “ Bi .
LCM is well implemented CbO: study of LCM from FCA point of view 51
The jumps with Di ‰ Bi are not desirable because they land on a closed set
which was already processed or will be processed later (depending on the direc-
tion of the sweep). CbO does not perform such jumps. The check of the condition
Di “ Bi is called a canonicity test.
Algorithm 2: Close-by-One
def GenerateFrom(A, B, y):
input : A – extent
B – set of attributes
y – last added attribute
1 D Ð AÒ
2 if Dy ‰ By then
3 return
4 print(xA, Dy)
5 for i P ty ` 1, . . . , nu z D do
6 C Ð A X iÓ
7 GenerateFrom(C, D Y tiu, i)
8 return
GenerateFrom(X, H, 0)
One can see the pseudocode of CbO in Algorithm 2. Firstly, we additionally
pass an extent A to the procedure GenerateFrom and the closed set B ÓÒ is
computed as AÒ (line 1), which is more efficient. Then the canonicity test is
performed. If it fails, we end the procedure (lines 2, 3). Otherwise, we print the
the concept and continue with the generation of its subtree.
Remark 2. What we show in Algorithm 2 is not the usual pseudocode of CbO
presented in literature. We made some superficial changes to emphasize the link
between CbO and LCM, which will be apparent later. Specifically:
(a) The closure and the canonicity test (lines 1–3) are usually performed before
the recursive invocation (line 7), not as a first steps of the procedures.
(b) The main loop (line 5) of CbO usually processes the attributes in ascending
order, which corresponds to a left-to-right depth-first sweep through the
tree of all subsets (Fig. 1). In actual fact, for CbO there is no reason for a
particular order of processing attributes.
4 Features of LCM
There are three versions of the LCM algorithm:
LCM1 is CbO with arraylist representation of data and computing of all ex-
tents at once (described in Section 4.2), data preprocessing (described in
Section 4.1), and using of diffsets [19] to represent extents for dense data
(this is not present in later versions).
52 Radek Janostik et al.
LCM2 is LCM1 (without diffsets) with conditional databases (described in Sec-
tion 4.3)
LCM3 is LCM2 which uses a hybrid data structure to represent a context.
The data structure uses a combination of FP-trees and bitarrays, called a
complete prefix tree, to handle the most dense attributes. Arraylists are used
for the rest, the same way as in the previous versions.
In this paper, we describe all features present in LCM2.
4.1 Initialization
To speed the computation up, LCM initializes the input data as follows:
‚ removes empty rows and columns,
‚ merges identical rows,
‚ sorts attributes by cardinality (|y Ó |) in descending order,
‚ sorts objects by cardinality p|xÒ |q in descending order.
In the pseudocode in Algorithm 3 (later in the paper), the initialization is
not shown and it is supposed that it is run before the first invocation of the
procedure GenerateFrom.
FCA aspect: The attribute sorting is well known to most likely cause a smaller
number of computations of closures in CbO-based algorithms [9,4,5]. This feature
is included in public implementations of In-Close4 and FCbO.
The object sorting is a different story. Andrews [4] tested the performance of
In-Close2 and concluded that lexicographic order tends to significantly reduce
L1 data cache misses. However, the test were made for bitarray representation
of contexts.
The reason for object sorting in LCM is probably that a lesser amount of
inverses occurs in a computation of a union of rows (shown later (5)), which
is consequently easier to sort. Our testing with Uno’s implementation of LCM
did not show any difference in runtime for unsorted and sorted objects when
attributes are sorted. In the implementation of LCM3, the object sorting is not
present.
Remark 3. In examples in the present paper, we do not use sorted data, in order
to keep the examples small.
4.2 Ordered arraylists and occurrence deliver
LCM uses arraylists6 as data representation of the rows of the context. It is
directly bound to one of LCM’s main features – occurrence deliver:
LCM computes extents A X iÓ (line 6 in Algorithm 2) all at once using a
single traversal through the data. Specifically, it sequentially traverses through
6
Whenever we write arraylist, we mean ordered arraylists.
LCM is well implemented CbO: study of LCM from FCA point of view 53
1) before occurence deliver 2) processing first row (object a)
items items
a 234578 a 234578
b 123457 b 123457
c 2367 c 2367
d,i 2 7 8 d,i 2 7 8
e,f,h 1 3 5 6 7 e,f,h 1 3 5 6 7 a a a a a a
g 57 1 2 3 4 5 6 7 8 g 57 1 2 3 4 5 6 7 8
3) processing second row (object b) 4) processing the rest (objects c–g)
items items g
a 234578 a 234578 e,f,h
b 123457 b 123457 d,i e,f,h g d,i
c 2367 c 2367 c c e,f,h c
d,i 2 7 8 b b b b b d,i 2 7 8 e,f,h b b b b e,f,h b d,i
e,f,h 1 3 5 6 7 b a a a a a a e,f,h 1 3 5 6 7 b a a a a c a a
g 57 1 2 3 4 5 6 7 8 g 57 1 2 3 4 5 6 7 8
Fig. 2. Occurrence deliver in LCM.
all rows xÒ of the context and whenever it encounters an attribute i, it adds x
to an initially empty arraylist – bucket – for i (see Fig. 2). As LCM works with
conditional datasets (see Section 4.3), attribute extents correspond to extents
A X iÓ (see Algorithm 2, line 6).
LCM generates childs of each node from right to left. That way, it can reuse
the memory for extents (buckets). For example, when computing extents in the
node t2u, that is t2, 3uÓ and t2, 4uÓ , the algorithm can reuse the memory used
by extents t3uÓ and t4uÓ , because t3u and t4u (and their subtrees) are already
finalized (see Fig. 3).
FCA aspect: In FCA, the CbO-based algorithms do not specify data represen-
tation used for handling contexts, sets of objects, and sets of attributes. This is
mostly considered a matter of specific implementations (see Remark 4). Gener-
ally, the data representation issues are almost neglected in literature on FCA.
The well-known comparison study [12] of FCA algorithms mentioned the need
to study the influence of data structures on practical performances of FCA al-
gorithms but it does not pay attention to that particular issue. The comparison
1
H
9 5 3 2
1 2 3 4
13 11 10 7 6 4
2 3 4 3 4 4
15 14 12 8
3 4 4 4
16
4
Fig. 3. Demonstration of bucket reuse in LCM with right-first sweep.
54 Radek Janostik et al.
study [10] provided the first steps to an answer for this need.7 The latter paper
concludes that binary search trees or linked lists are good choices for large or
sparse datasets, while bitarray is an appropriate structure for small or dense
datasets. Arraylists did not perform particularly well in any setting. However,
this comparison did not assume other features helpful for this data representa-
tion, like conditional databases (see Section 4.3) and computation of all required
attribute extents in one sweep by occurrence deliver. More importantly, the min-
imal tested density is 5 %, which is still very dense in the context of transactional
data.
Remark 4. Available implementations of FCbO8 and In-Close9 utilize bitarrays
for rows of contexts, and sets of attributes, and arraylists for sets of objects.
4.3 Conditional Database and Interior Intersections
LCM reduces the database for the recursive invocations of GenerateFrom to
so-called conditional databases.
Let K “ xX, Y, Iy be a formal context, B be an intent, and y be the attribute
used to build B. The conditional database (context) KB,y w.r.t. xB, yy is created
from K as follows:
(a) First, remove objects from K which are not in the corresponding extent
A “ BÓ.
(b) Remove attributes which are full or empty.
(c) Remove attributes lesser than y. 10
(d) Merge identical objects together.
(e) Put back attributes removed in step (c); set each new object created in
step (d) by merging objects x1 , . . . , xk P X to have attributes common to
the objects x1 , . . . , xk . That is, the merged objects are intersections of the
original objects. The part of the context added in this step is called an
interior intersection.
Alternatively, we can describe conditional databases with interior intersections
as:
‚ Restricting the context K to objects in A and attributes in N where
˜ ¸
ď
Ò
N“ x z AÒ . (5)
xPA
This covers the steps (a)–(c).
7
Paper [10] compares bitarrays, sorted linked lists, arraylists, binary search trees, and
hash tables.
8
Available at http://fcalgs.sourceforge.net/.
9
Available at https://sourceforge.net/projects/inclose/.
10
In the implementation, when the database is already too small (less than 6 objects,
and less than 2 attributes), steps (c)–(d) are skipped.
LCM is well implemented CbO: study of LCM from FCA point of view 55
‚ Subsequent merging/intersecting of those objects which have the same inci-
dences with attributes in t1, 2, . . . , y ´ 1u. This covers the steps (d)–(e).
Note, that from the conditional database (with interior intersections) KB,i all
intents in the subtree of B can be extracted. More specifically, if D is an intent
of the conditional database and it passes the canonicity test (tested on interior
intersections) then D Y B is an intent of the original context which passes the
canonicity test; i.e. is in the subtree of B.
In pseudocode in Algorithm 3 (later in the paper), the creation of the con-
ditional databases with interior intersections is represented by the procedure
named CreateConditionalDBpK, A, N, yq.
FCA aspect: CbO-based algorithms do not utilize conditional databases. How-
ever, we can see partial similarities with features of CbO-based algorithms.
First, all of the algorithms skip attributes in B and work only with part of
the formal context given by B Ó and Y z B. This corresponds to step (a) and the
first part of step (b) (full attributes).
Second, the removal of empty attributes in step (b) utilizes basically the same
idea as in In-Close4 [6]: if the present extent A and an attribute extent iÓ have
no common object, we can skip the attribute i in the present subtree. In FCbO
and In-Close3, such attribute would be skipped due to pruning (see Section 4.4).
Steps (c)–(e) have no analogy in CbO algorithms.
Pseudocode of LCM without pruning
At this moment, we present pseudocode of LCM (Algorithm 3) with above-
described features. As in the case for CbO, the algorithm is given by recursive
procedure GenerateFrom. The procedure takes four arguments: an extent A, a
set of attributes B, the last attribute y added to B, and a (conditional) database
K). The procedure performs the following steps:
(line 1) The set N (5) of non-trivial attributes is computed.
(line 2) The frequencies of all attributes in N are computed, this is made
by a single traversal through K similar to the occurence deliver
(described in Section 4.2).
(lines 3–5) The loop checks whether any attribute in N lesser than y has
frequency equal to |A|. If so, the attribute causes the canonicity
test to fail, therefore we end the procedure.
(lines 6–9) The loop closes B (and updates N ) based on the computed fre-
quencies.
(line 10) As the cannonicity is checked and B is closed, we can output
xA, By.
(line 11) The conditional database KB,y (described in Sec. 4.3) is created.
(line 12) Attribute extents from KB,y are computed using occurence deliver
(described in Section 4.2).
56 Radek Janostik et al.
Algorithm 3: LCM (without pruning)
def GenerateFrom(A, B, y, K):
input : A – extent
B – set of attributes
y – last added attribute
K – input context/conditional database
`Ť Ò
˘
1 NÐ xPA x zB
2 tni | i P N u ÐFrequencies(K, N )
3 for i P N, i ă y do
4 if ni “ |A| then
5 return
6 for i P N, i ą y do
7 if ni “ |A| then
8 B Ð B Y tiu
9 N Ð N z tiu
10 print(xA, By)
11 K1 Ð CreateConditionalDB(K, A, N , y)
12 tCi | i P N u Ð OccurenceDeliver(K1 )
13 for i P N, i ą y, (in descending order) do
14 GenerateFrom(Ci , B Y tiu, i, K1 )
15 return
GenerateFrom(X, X Ò , 0, xX, Y, Iy)
(lines 13–14) The procedure GenerateFrom is recursively called for attributes
in N with the conditional database KB,y and the corresponding
attribute extent.
4.4 Bonus Feature: Pruning
The jumps using closures in CbO significantly reduce the number of visited nodes
in comparison with the naı̈ve algorithm. The closure, however, becomes the most
time consuming operation in the algorithm. The pruning technique in LCM11
avoids computations of some closures based on the monotony property: for any
set of attributes B, D Ď Y satisfying B Ď D, we have
j P pB Y tiuqÓÒ implies j P pD Y tiuqÓÒ . (6)
When i, j R D and j ă i, the implication (6) says that if j causes pB Y tiuqÓÒ to
fail the canonicity test then it also causes pD Y tiuqÓÒ to fail the canonicity test.
That is, if we store that pB Y tiuqÓÒ failed, we can use it to skip computation of
the closure pD Y tiuqÓÒ for any D Ą B with j R D.
11
Pruning is not described in papers on LCM, however, it is present in the implemen-
tation of LCM2.
LCM is well implemented CbO: study of LCM from FCA point of view 57
Due to the page limit, we skip details here.
FCA aspect: Similar pruning is also present in FCbO and In-Close3+. LCM’s
pruning is weaker than the pruning in FCbO and In-Close3, stronger than the
pruning in In-Close4, and incomparable with pruning in In-Close5.
5 Frequency Counting
In previous sections, we did not take into account the frequency of itemsets, as
in FCA, the frequency is not usually assumed. However, the implementations
of FCbO and In-Close4 allow us to pass minimum support as a parameter, and
then enumerate only frequent intents.
The CbO-based algorithms utilize a simple apriori principle: if a set is in-
frequent then all its supersets are infrequent. That directly translates into the
tree-like computation of the algorithms – if a node represents an infrequent set,
then its subtree does not contain any frequent set.
In LCM, we make the following modification of the features described in
Section 4.
Data representation – each arraylist is accompanied with weight, i.e. number of
objects it corresponds to.
Initialization – additionally, infrequent attributes are removed and the weights
of rows are set to reflect the number of merged rows (1 for unique rows).
Conditional databases – in step (b), infrequent attributes are removed as well;
and in step (d), the weights of rows are updated.
6 Conclusions
We analyzed LCM from the point of view of FCA and concluded that it is
a CbO-based algorithm with additional features directed towards processing
sparse data. We also compared the additional features with those of FCbO and
InClose2+.
Future research: We see two main directions for our upcoming research:
– The investigation of other algorithms for closed frequent itemset mining and
putting them into context with FCA algorithms.
– Experimental evaluation of the incorporation of LCM’s features in CbO-
based algorithms; this could lead to fast implementations of the algorithms.
Acknowledgment: The authors acknowledge support by the grants:
– IGA 2018 of Palacký University Olomouc, No. IGA PrF 2019 034,
– JG 2019 of Palacký University Olomouc, No. JG 2019 008.
References
1. Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen,
A Inkeri Verkamo, et al. Fast discovery of association rules. Advances in knowledge
discovery and data mining, 12(1):307–328, 1996.
2. Gabriela Alexe, Sorin Alexe, Tibérius O Bonates, and Alexander Kogan. Logi-
cal analysis of data–the vision of Peter L. Hammer. Annals of Mathematics and
Artificial Intelligence, 49(1-4):265–312, 2007.
58 Radek Janostik et al.
3. Gabriela Alexe and Peter L. Hammer. Spanned patterns for the logical analysis of
data. Discrete Applied Mathematics, 154(7):1039–1049, 2006.
4. Simon Andrews. In-Close2, a high performance formal concept miner. In Proceed-
ings of the 19th International Conference on Conceptual Structures for Discovering
Knowledge, ICCS’11, pages 50–62, Berlin, Heidelberg, 2011. Springer-Verlag.
5. Simon Andrews. A ‘Best-of-Breed’ approach for designing a fast algorithm for
computing fixpoints of Galois connections. Information Sciences, 295:633–649,
2015.
6. Simon Andrews. Making use of empty intersections to improve the performance of
CbO-type algorithms. In International Conference on Formal Concept Analysis,
pages 56–71. Springer, 2017.
7. Simon Andrews. A new method for inheriting canonicity test failures in Close-by-
One type algorithms. In CLA, volume 2123, pages 255–266, 2018.
8. Roberto J. Bayardo Jr. Efficiently mining long patterns from databases. In ACM
Sigmod Record, volume 27, pages 85–93. ACM, 1998.
9. Petr Krajca, Jan Outrata, and Vilem Vychodil. Advances in algorithms based on
CbO. In CLA, volume 672, pages 325–337, 2010.
10. Petr Krajca and Vilem Vychodil. Comparison of data structures for computing
formal concepts. In International Conference on Modeling Decisions for Artificial
Intelligence, pages 114–125. Springer, 2009.
11. Sergei O. Kuznetsov. A fast algorithm for computing all intersections of objects
from an arbitrary semilattice. Nauchno-Tekhnicheskaya Informatsiya Seriya 2-
Informatsionnye Protsessy i Sistemy, (1):17–20, 1993.
12. Sergei O. Kuznetsov and Sergei Obiedkov. Comparing performance of algorithms
for generating concept lattices. Journal of Experimental and Theoretical Artificial
Intelligence, 14:189–216, 2002.
13. Heikki Mannila and Hannu Toivonen. Multiple uses of frequent sets and condensed
representations. In KDD, volume 96, pages 189–194, 1996.
14. Jan Outrata and Vilem Vychodil. Fast algorithm for computing fixpoints of Galois
connections induced by object-attribute relational data. Information Sciences,
185(1):114–127, 2012.
15. Takeaki Uno, Tatsuya Asai, Yuzo Uchida, and Hiroki Arimura. LCM: An efficient
algorithm for enumerating frequent closed item sets. In FIMI, volume 90. Citeseer,
2003.
16. Takeaki Uno, Tatsuya Asai, Yuzo Uchida, and Hiroki Arimura. An efficient algo-
rithm for enumerating closed patterns in transaction databases. In International
Conference on Discovery Science, pages 16–31. Springer, 2004.
17. Takeaki Uno, Masashi Kiyomi, and Hiroki Arimura. LCM ver. 2: Efficient mining
algorithms for frequent/closed/maximal itemsets. In FIMI, volume 126, 2004.
18. Takeaki Uno, Masashi Kiyomi, and Hiroki Arimura. LCM ver. 3: collaboration of
array, bitmap and prefix tree for frequent itemset mining. In Proceedings of the
1st international workshop on open source data mining: frequent pattern mining
implementations, pages 77–86. ACM, 2005.
19. Mohammed J. Zaki and Karam Gouda. Fast vertical mining using diffsets. In
Proceedings of the ninth ACM SIGKDD international conference on Knowledge
discovery and data mining, pages 326–335. ACM, 2003.