Several parallel and distributed FCA algorithms have been proposed to speedup the discovery of concepts. Some require the context to be replicated on all machines while others partition the context horizontally across different machines. The former suffers from memory bottlenecks for large contexts as every machine retains the entire context in memory. The latter approaches are based on Map-Reduce paradigm wherein to compute a valid concept requires all-all communication between different machines, incurring huge communication overheads. It has been shown that DFS (Depth-First-Search) based approaches can exploit database reduction strategy for concept sub-tree exploration. This significantly decreases the cost of closure computation in the concept sub-tree and results in higher speedup. The existing Map-Reduce based approaches cannot use DFS exploration strategy. In this paper, we propose a hybrid partitioning strategy for distributed FCA that uses horizontal partitioning for groups of low support attributes and vertical partitioning for high support attributes. This not only alleviates memory bottlenecks but also minimizes communication overheads. For vertically partitioned sub-context, inter-machine communication is only required for concepts below a certain support threshold. We further minimize the communication cost by using group-id based auxiliary structure. This hybrid partitioning also allows DFS based concept exploration, thereby making it more scalable and efficient.
Formal Concept Analysis (FCA) is a method of data analysis that aims at
extracting natural clusters (formal concepts) from object and attribute data table
(a.k.a. context). The sequential algorithms for computing concepts (e.g.
CloseBy-One (CbO) [
It has been shown that DFS based approaches can exploit database reduction
for concept sub-tree exploration. This significantly decreases the cost of closure
computation in the concept sub-tree and results in higher speedup. The existing
MR-based approaches cannot use DFS exploration strategy as it would make
them highly inefficient. If they compute one concept at a time using DFS, they
would incur large waiting time due to all-all communication between the
machines. Hence, they explore the concept tree in a breadth-first manner and try
to overlap communication and computation. However, they lose the benefits of
database reduction available in DFS based approach. From experiments, we find
that the distributed MR-based algorithms perform slower than even single node
DFS based algorithms like LCM [
In this paper, we propose a hybrid partitioning strategy for distributed FCA that uses horizontal partitioning for groups of low support attributes and vertical partitioning for high support attributes (see Fig. 1). This partitioning strategy allows DFS based concept exploration, alleviates memory bottlenecks and minimizes communication overheads. Hence, it is more scalable and efficient than existing algorithms. We also propose some optimizations for reducing inter-machine communication cost by using group-id based auxiliary structure.
Rest of the paper is organized as follows: Section 2 introduces the relevant background and related work; Section 3 discusses the hybrid partitioning strategy and the optimizations for reducing inter-machine communication cost; Section 4 describes the performance results and Section 5 discusses the conclusion and future work of this paper. 2 2.1
In this section, we introduce the relevant notations and terminology of FCA. Definition 1 A formal context K = (G, M, I), consists of two sets G and M , and a binary relation I ⊆ G×M . G represents the set of objects and M represents the set of attributes. If g ∈ G and m ∈ M are in relation I, we write (g, m) ∈ I or gIm. It can be read as “object g has attribute m”.
Formal concept is computed using two operators ↑ and ↓. ↓↑ is a closure
operator [
A formal concept is described by an extent and an intent as shown below: Definition 4 A duplet hA, Bi is called formal concept of context K = (G, M, I), if A ⊆ G and B ⊆ M , A↑ = B, and A = B↓. The set A (object set) is called the extent and the set B (attribute set) is called the intent of the concept. 2.2
Linear time Closed itemset Miner (LCM) [
There are both parallel and distributed implementations of the LCM algorithm.
P-LCM [
MR-CbO [
Yoshizoe et al. [
In summary, existing parallel and distributed versions of LCM either work on replicated context or horizontally partitioned context. The former suffers from memory bottlenecks for large contexts as every machine retains the entire context in memory. The latter approaches incur huge communication overheads and are not able to explore the concept tree using DFS based strategy. 3
We propose G-LCM, a group-based LCM algorithm that scales to large contexts. G-LCM uses a hybrid partitioning strategy to bound the communication cost as well as the memory consumption across machines. 3.1
Hybrid partitioning is a technique that uses horizontal partitioning for low support attributes and vertical partitioning for high support attributes (above certain support threshold). The context is reordered according to the support of the attributes. For creating horizontal partitions, we start with the attribute having the lowest support and form groups of attributes in an increasing order of their support by fixing an upper bound on the total number of objects in a group.
Thus, the low support attributes are grouped into many horizontal partitions, each of which can be stored in a single machine. The high support attributes are grouped into a single vertical partition containing only the frequent attributes in each of its objects. This enables us to compress the vertical partition since many objects in this group would become identical and can be coalesced.
We use 3 Hadoop Map-Reduce jobs to partition the input context. Job1 computes the support of attributes; job2 reorders the attributes based on their support and job3 partitions the context based on the grouping strategy. 3.1.1 Horizontal Partitioning: The sub-context induced by a group of attributes is referred as a horizontal partition. Consider a formal context K = (G, M, I) relabeled according to support of the attributes; the attribute with the lowest support is assigned the lowest index.
Definition 5 Suppose attributes are indexed and arranged in the ascending order of their support as m1, m2, ... m|M|. The grouping strategy partitions the attributes linearly into (say r + 1-groups): R1, R2, ...,Rr, and R0. 1. Each horizontal partition, Ri = {mk | mk ∈ M, k ∈ [L(i), U (i)]} 2. Vertical partition (R0) = {mk | mk ∈ M, support(mk) ≥ minT h} L(i) = U (i) = 1,
if i = 1 U (i − 1) + 1, if 1 < i ≤ r
j j | j < |M | and X support(mk) ≤ θ < j+1
X support(mk) k=L(i) k=L(i) Where, θ is upper bound on the number of objects in a partition and support(mk) returns the cardinality of m↓k.
Suppose that K is partitioned into k horizontal partitions each having groupid in [1, r](see Fig. 1). While forming groups of attributes, we ensure that the total number of objects in their corresponding partitions is less than or equal to a threshold θ. Consider a toy context shown in Table 1 consisting of four attributes and four objects. The relabelled context after sorting the attributes according to support is shown in Table 2. Assume that the upper bound θ = 2, then NYC and DEL are the frequent attributes. The two horizontal partitions are formed with group attribute set {BOM } and {LON } respectively. Group 1 contains objects 1 and 4 (See Table 3). Group 2 contains objects 2 and 4 (see Table 4).
Definition 6 The sub-context induced by Rk, k > 0, is known as the horizontal partition, Kk = (Gk, Mk, Ik) and is defined as: Gk = Sm∈Rk (m↓), where m↓ is the set of objects in K containing attribute m, Mk = Sg∈Gk (g↑), where g↑ is the set of attributes in K containing object g, and Ik = (Gk × Mk) ∩ I. ↑k and ↓k denote the corresponding concept forming operators in Kk.
Lemma 1. Every concept (A, B) generated by the horizontal partition Kk that includes at least one attribute m ∈ Rk as part of its intent (i.e. m ∈ B) is valid in the entire context (G, M, I).
Proof. Suppose (A, B) is not closed in K. Then by extensivity of closure operator, B ⊆ B↓↑. Let n ∈ B↓↑ \ B. =⇒ ∀g ∈ B↓ : gIn Consider an attribute m ∈ Rk s.t. m ∈ B =⇒ ∀g ∈ B↓ : gIm =⇒ B↓ ⊆ m↓ =⇒ B↓ ⊆ Gk (m ∈ Rk) =⇒ B↓ = B↓k (By definition of Ik) But B↓k = A (((A,B) is closed in Kk) =⇒ ∀g ∈ A : gIn =⇒ n ∈ B
(hence, proved by contradiction) 3.1.2 Vertical Partitioning: Vertically partitioned context is defined w.r.t. a support threshold and is assigned group-id 0. It contains the union of occurrences of all attributes whose support is greater than the threshold. Vertical partition with support threshold 3 is shown in Table 5.
Definition 7 The vertically partitioned context K0 = (G0, M0, I0) w.r.t. support threshold (minT h) is defined as: M0 ⊆ M s.t. ∀m ∈ M0, support(m) ≥ minT h, G0 = G and I0 = (G0 × M0) ∩ I. 3.2
As the vertical partition does not include all the attributes, it can lead to discovery of invalid concepts in certain cases. For example closure of {NYC, DEL} in vertical partitioned context is {NYC, DEL} but the actual closure in the input context is {LON, NYC, DEL}. From this example, it is clear that the vertical partition may generate invalid concepts. Hence, we augment the vertically partitioned context with auxiliary information that will help check validity of the concept. We define the augmented context for the vertical partition. Definition 8 An augmented context Kac = (Gac, Mac, Iac) is defined as: Gac = G, Mac = {m(k) | 1 ≤ k ≤ r}, where r is the number of horizontal partitions and gIacm(k) iff ∃m ∈ Rk s.t. gIm.
Lemma 2. Let ↑a denote the ↑ operator in Kac. A concept (Av, Bv) generated by the vertical partition is valid if for every horizontal partition Kk : m(k) ∈ Av↑a there exists no attribute m ∈ Rk s.t. Av ⊆ m↓k .
Proof. Assume there exists an attribute m ∈ Rk s.t. Av ⊆ m↓k . =⇒ ∀g ∈ Av : gIm =⇒ m ∈ Av↓. But Av↓ = Bv and m ∈/ Bv. Hence proved.
For each concept generated by the vertical partition, we intersect the group-ids of the objects in the extent (using the augmented context). If the intersection returns an empty set, then the concept is valid, else an additional check is required to test the validity of the concept. For example, suppose that we make 2 groups in our toy context; attributes in group 0 (vertical partition) contain NYC and DEL, while attributes in group 1 (horizontal partition) contain BOM and LON. Group 0 includes all 4 objects. In the augmented context, each object will contain group-id 1 except object 3. Hence, for concept intent {DEL} in the augmented context, the group-id intersection returns {1}. This however does not mean that {DEL} is an invalid concept intent. We need to test its validity w.r.t. attributes in group 1. In this case, we find that no attribute in group 1 includes the extent of {DEL}, and therefore {DEL} is a valid concept intent.
Thus, group-id based intersection may generate false positives but no false
negatives. To understand how false positives are handled, let us assume a
scenario in which, machine M0 is discovering concept in vertical partition; where
as machine M1 and M2 are discovering concepts in group 1 and 2 (horizontal
partitions) respectively. In machine M1 and M2, a hash table is created with
keys as the low support attributes (m) of the corresponding group and value
being the corresponding attribute’s object ids (m↓). To check the validity of the
concept (Av, Bv) discovered in the vertical partition, a validity check is issued to
all the machines whose id is returned by the group-id based intersection. Upon
receiving this query, each machine checks in its hash table whether the extent
Av is a subset of the value stored against any attribute id of that group. If a
match is found, then the concept discovered by the vertical partition is invalid.
This check can be implemented efficiently using a Cuckoo filter.
3.2.1 Cuckoo filter Cuckoo filter is a probabilistic data structure that checks
the membership of an element in a set. It is mainly designed for applications that
need to store many elements in the set and check the membership of the set with
low false positive rate. Cuckoo filter is variant of cuckoo hash table that stores
only fingerprints instead of (key, value) pairs which leads to space efficient filter
and restricts false positive rate to less than 3% [
For each attribute (m ∈ Rk), we store its object IDs (m↓) in a cuckoo filter. To test the validity of a concept intent, we first determine the candidate horizontal partitions using the augmented context. Then for each candidate partition, we check the concept extent against the cuckoo filter of those attributes whose support is greater than the size of the extent. If the cuckoo filter returns negative for any object in the concept extent, it means that the concept intent does not include that attribute. Otherwise, the attribute can be present with high probability and needs to be verified by actual comparison of the concept extent with the concerned attribute’s extent. 3.2.2 G-LCM algorithm for discovering the concepts in vertical partition Algorithm 1 shows how concepts are discovered in the vertical partition. In line number 2, algorithm iterates over the (M 0) attribute set. In line number 4, it checks whether the newly found concept is redundant or not using function isN ewConcept similar to LCM (see Section 2.2). If the support of the new concept is below the threshold (line 5), then it performs the validity check locally using group-id based intersection function (line 6). If that returns a non-empty set (line 7) then for each group-id in gIDList (groupid list), a membership query is sent to the machine which holds that groupid context (lemma 2). On that machine, the cuckoo filter is used to check the validity of the concept (line 8). As cuckoo filter may produce false positives, we do an actual comparison with the extent if the cuckoo filter returns true (lines 11 - 18). If the extent is having some common attributes in the group-id context then it is a true positive (line 14) else false positive (line 16).
In case the support of the newly found concept is greater than minimum threshold (minT h) then the extent of the concept does not have any common attribute from infrequent attributes. Thus, the concept found is valid (line 19). In the next section, we discuss experimental evaluation of this algorithm. 4
We implemented G-LCM algorithm in Java. The context is partitioned into
horizontal and vertical partitions using Map-Reduce jobs. For horizontal partitions,
we can use the distributed LCM algorithm from [
Here, we report performance results for computing concepts in the vertical partition for susy and pumsb_star data-sets. The susy data-set 1 contains 190 attributes and 5 million objects with average object length as 19.
We evaluate the efficacy of group-id based intersection and cuckoo filter for different values of support threshold. When group-id based intersection function returns an empty set, no inter-machine communication is necessary to test the validity of the concept. In Table 7, the true negative column (T Ng) captures the frequency of such occurrences in susy dataset. If the function returns a non-empty set (gIDList) then for each group-id in gIDList, we need to check whether the 1 FIMI repository, http://fimi.cs.helsinki.fi/. Last accessed 1 March 2020 concept is valid/invalid. If the group has at least one attribute containing the extent, then the concept is invalid. As the group-id based intersection did not detect this, it is counted as False Positive ((F Pg)). Otherwise the concept is valid (T Pg). We observe that the group-id based intersection returns an empty set (T Ng) almost 100% times for susy data-set. This means that concepts discovered in the vertical partition are valid and there is no need for inter-machine communication.
For experiments on pumsb_star data-set 2(containing 49046 objects, 2088 attributes with average object length as 50.48), we found that group-id based intersection returned a non-empty set (F Pg) close to 50% (see Table 8 for pumsb_star data-set). Here, we need to communicate with a machine whose group-id is contained in the list returned by group-id based intersection. Still group-based auxiliary structure reduces the communication cost significantly as communication is required only with the machines storing the partition corresponding to that group and not all of them. On the machine, the validity check is performed using cuckoo filter. If cuckoo filter returns false ( T Nc), then the concept is valid in the vertical partition. In such cases, no comparison with the actual context of the horizontal partition is necessary. From Table 8, we see that cuckoo filter always returns true negative ( T Nc).
Our experiments show that group-id based auxiliary structure decreases the inter-machine communication cost for testing validity of discovered concepts by almost 100% for susy data-set and up to 50% for pumsb_star data-set. Cuckoo filter reported 0% false positives (F Pc) thereby further minimizing the cost of validity checks. 5
In this paper, we proposed a novel hybrid partitioning technique that uses
horizontal partitioning for low support attributes and vertical partitioning for high
support attributes. This technique ensures that the size of each partition does
not exceed single machine’s memory. Thus, it becomes possible to use the
distributed LCM algorithm [
This research was supported by SPARC, a Government of India Initiative under grant no. SPARC/2018-2019/P682/SL. We thank Dr. Sergei Obiedkov from HSE Moscow for his helpful comments in coming up with the paritioning strategy.