Handling the Complexity of Computing Maximal Consistent Blocks

Abstract

The maximal consistent blocks technique, adopted from discrete mathematics, describes the maximal collection of objects, in which all objects are indiscernible in terms of available information. In this paper, we estimate the total possible number of maximal consistent blocks and prove that the number of such blocks may grow exponentially with respect to the number of attributes for incomplete data with “do not care” conditions. Results indicate that the time complexity of some known algorithms for computing maximal consistent blocks has been underestimated so far. Taking into account the complexity, for the practical usage of such blocks, we propose a performance improvement involving the parallelization of the maximal consistent blocks construction method.

1. Introduction

Rough set theory [1,2] is a tool for data mining and knowledge discovery, initially developed for complete information systems [3,4] and then extended for incomplete systems [5,6,7,8,9,10,11,12,13,14,15]. Maximal consistent blocks, as a maximal collection of indiscernible objects, were introduced for incomplete data sets, with missing values represented only as “do not care” conditions, and were used as basic granules to define only ordinary lower and upper approximations in [16]. In [17,18], the definition of maximal consistent blocks was generalized to cover lost values. Furthermore, two new types of approximations were introduced, global probabilistic approximations and saturated probabilistic approximations based on maximal consistent blocks [19,20,21].

Several approaches for computing maximal consistent blocks: the brute force method [22], the recursive method [22] and the hierarchical method [23] were introduced for incomplete data sets with only “do not care” conditions. For incomplete data sets with only lost values, the simplified recursive method based on the property that for such data sets, the characteristic relation is transitive, was provided in [24]. In turn, in [17], the method for computing maximal consistent blocks for arbitrary interpretations of missing attribute values based on a characteristic relation was proposed.

Analysis of the published algorithms for constructing maximal consistent blocks, for data with only “do not care” conditions, revealed two problems. Firstly, the obtained blocks might not be maximal, especially for data sets for which a characteristic relation is not transitive. The second problem is that, in some cases, the reported computational complexity of the algorithms is underestimated [25]. Additionally, in papers [18,26], during the comparison of characteristic sets with generalized maximal consistent blocks in terms of an error rate and complexity of induced rule sets, the authors suggested that characteristic sets can be computed in polynomial time, while computing maximal consistent blocks is associated with exponential time complexity for incomplete data with “do not care” conditions.

In this paper, we estimate the total number of maximal consistent blocks for incomplete data sets. We define a special data set called a k-galaxy set, and we prove that the number of maximal consistent blocks grows exponentially with respect to the number of attributes for incomplete data with all missing attribute values interpreted as “do not care” conditions. Additionally, for the practical usage of this technique of incomplete data set mining, we propose a performance improvement in the form of the parallelization of the maximal consistent blocks construction method.

The paper is organized as follows. In Section 2, Section 3 and Section 4, an appropriate introduction to the used approach for incomplete data mining is presented. In Section 5, the complexity of computing maximal consistent blocks is estimated. Finally, a parallel solution for determining maximal consistent blocks is proposed in Section 6.

2. Incomplete Data

We consider incomplete data sets with two interpretations of missing attribute values—lost values and “do not care” conditions. Lost values, denoted by question marks, are interpreted as values that are erased or not inserted. The “do not care” conditions, denoted by stars, have another interpretation. Here, we assume that the original values are irrelevant so that such values may be replaced by any existing attribute value [27]. The practice of data mining shows that “do not care” conditions are often the results of the refusal to provide a value. For example, some respondents refuse to provide a value of the salary attribute, or, when asked for eye color during the collection of data about a disease, may consider such an attribute as irrelevant and again refuse to specify the value. It is worth noting that there are also other interpretations of missing attribute values, such as not applicable. An example of such a situation can be the value of the salary attribute when a respondent is unemployed. It is important to understand the reasons and distinguish between various types of missing data, such as missing completely at random, missing at random, and missing not at random. Examples can be found in the statistical literature on missing attribute values [28,29].

The incomplete data set, in the form of a decision table, is presented in

Table 1. An incomplete data set.

	Attributes			Decision
Case	Mileage	Accident	Equipment	Buy
1	medium	yes	low	yes
2	?	no	*	yes
3	long	no	?	yes
4	medium	*	low	yes
5	long	yes	?	no
6	*	*	high	no
7	?	*	low	no
8	medium	*	high	no

. The rows of the decision table represent cases or objects. The set of all cases is called the universe and is denoted by U. Table 1 shows U = {1, 2, 3, 4, 5, 6, 7, 8}. The independent variables are called attributes and are denoted by A. In Table 1, Mileage, Accident and Equipment are the attributes. The set of all values of the attribute a is called a domain of a and is denoted by $V_a$. In Table 1, $V_{Equipment}=\{low,high\}$. The dependent variable Buy is called a decision. The set of all cases with the same decision value is called a concept. In Table 1, there are two concepts, the set {1, 2, 3, 4} of all cases, where the value of Buy is yes and the other set {5, 6, 7, 8}, where the value of Buy is no.

The value v of the attribute a for the case x is denoted by $a\left(x\right)=v$. A block of the attribute–value pair, denoted by $\left[\right(a,v\left)\right]$, is the set of all cases from U that for the attribute a have the value v, $\{x\in U|a\left(x\right)=v\}$.

We consider two interpretations of missing attribute values: lost values denoted by ? and “do not care” conditions denoted by ∗ in Table 1. The set of all cases from U that for the attribute a have lost values $\{x\in U|a\left(x\right)=?\}$ is denoted by $\left[\right(a,?\left)\right]$, whereas the set of all cases from U that for the attribute a have “do not care” conditions $\{x\in U|a\left(x\right)=\ast \}$ is denoted by $\left[\right(a,\ast \left)\right]$.

For incomplete decision tables, the definition of a block of an attribute–value pair is modified as follows [27]:

–

If for an attribute a and a case x, $a\left(x\right)=?$, then the case x should not be included in any blocks $\left[\right(a,v\left)\right]$ for all values v of the attribute a;

–

If for an attribute a and a case x, $a\left(x\right)=\ast$, then the case x should be included in blocks $\left[\right(a,v\left)\right]$ for all specified values v of the attribute a.

For Table 1, all the blocks of attribute–value pairs are as follows:

• $\left[\right(Mileage,medium\left)\right]=\{1,4,6,8\}$,
• $\left[\right(Mileage,long\left)\right]=\{3,5,6\}$,
• $\left[\right(Accident,yes\left)\right]=\{1,4,5,6,7,8\}$,
• $\left[\right(Accident,no\left)\right]=\{2,3,4,6,7,8\}$,
• $\left[\right(Equipment,low\left)\right]=\{1,2,4,7\}$,
• $\left[\right(Equipment,high\left)\right]=\{2,6,8\}$.

3. Characteristic Relation

In an incomplete decision table, for $B\subseteq A$, the objects of the pair $(x,y)\in U$ are considered similar in terms of the B-characteristic relation $R\left(B\right)$ defined as follows [12]:

$$(x,y)\in R\left(B\right)ifandonlyify\in K_B\left(x\right),$$

where $K_B\left(x\right)$ is the characteristic set, i.e., the smallest set of cases that are indistinguishable from $x\in U$, for all attributes from $B\subseteq A$. For incomplete decision tables, the characteristic set is defined as follows [11]:

–

If $a\left(x\right)$ is specified, then $K(x,a)$ is the block $\left[\right(a,a\left(x\right)\left)\right]$ of the attribute a and its value $a\left(x\right)$;

–

If $a\left(x\right)=?$ or $a\left(x\right)=\ast$, then $K(x,a)=U$.

For the data set from Table 1 and $B=A$, the characteristic sets are as follows:

• $K_A\left(1\right)=\{1,4\}$,
• $K_A\left(2\right)=\{2,3,4,6,7,8\}$,
• $K_A\left(3\right)=\{3,6\}$,
• $K_A\left(4\right)=\{1,4\}$,
• $K_A\left(5\right)=\{5,6\}$,
• $K_A\left(6\right)=\{2,6,8\}$,
• $K_A\left(7\right)=\{1,2,4,7\}$,
• $K_A\left(8\right)=\{6,8\}$.

The characteristic relation is $R\left(A\right)$ = {(1, 1), (1, 4), (2, 2), (2, 3), (2, 4), (2, 6), (2, 7), (2, 8), (3, 3), (3, 6), (4, 1), (4, 4), (5, 5), (5, 6), (6, 2), (6, 6), (6, 8), (7, 1), (7, 2), (7, 4), (7, 7), (8, 6), (8, 8)}.

4. Maximal Consistent Blocks

Maximal consistent blocks were introduced for incomplete data sets, in which all missing attribute values are “do not care” conditions, in [16]. The set X, $X\subseteq U$, is consistent with respect to B, $B\subseteq A$, if $(x,y)\in R\left(B\right)$ for any $x,y\in X$. Maximal consistent blocks were defined as a maximal collection of objects, in which all objects are consistent. If there does not exist a subset $Y\subseteq U$ such that $X\subseteq Y$, and Y is consistent with respect to B, then X is called a maximal consistent block of B. The set of all maximal consistent blocks of B is denoted by $\mathcal{C}\left(B\right)$. Following [16], the set of all maximal B-consistent blocks, which include an object $x\in U$, is denoted by $\mathcal{C}\left(B\right)\left(x\right)$.

The definition of maximal consistent blocks, extended to two interpretations of missing attribute values, lost and “do not care” conditions, was introduced in [18]. The set X, $X\subseteq U$ is consistent with respect to B, $B\subseteq A$, if $(x,y)\in R\left(B\right)$ for any $x,y\in X$. If there does not exist a consistent subset Y of U such that X is a proper subset of Y, the set X is called a maximal consistent block of B.

For the data set from Table 1 and $B=A$, the set $\mathcal{C}\left(A\right)$ of all maximal consistent blocks of A is $\left\{\right\{1,4\},\{2,6\},\{2,7\},\{3\},\{5\},\{6,8\left\}\right\}$. The collections of maximal consistent blocks with respect to objects determined by A are as follows:

• $\mathcal{C}\left(A\right)\left(1\right)=\left\{\right\{1,4\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(2\right)=\left\{\right\{2,6\},\{2,7\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(3\right)=\left\{\right\{3\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(4\right)=\left\{\right\{1,4\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(5\right)=\left\{\right\{5\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(6\right)=\left\{\right\{2,6\},\{6,8\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(7\right)=\left\{\right\{2,7\left\}\right\}$,
• $\mathcal{C}\left(A\right)\left(8\right)=\left\{\right\{6,8\left\}\right\}$.

The relation $S\left(B\right)$, $B\subseteq A$ and $x,y\in U$, formed from all possible pairs $(x,y)$ such that x and y are members of the same maximal B-consistent block, is called implied by the family $\mathcal{C}\left(B\right)$ of maximal consistent blocks. The relation $S\left(B\right)$ is symmetric. For data sets with all missing attribute values interpreted as lost, the relation $S\left(B\right)$ is transitive [18]. For the data set from Table 1, $S\left(A\right)$= {(1, 1), (1, 4), (2, 2), (2, 6), (2, 7), (3, 3), (4, 1), (4, 4), (5, 5), (6, 2), (6, 6), (6, 8), (7, 2), (7, 7), (8, 6), (8, 8)}.

5. Estimation of the Number of Maximal Consistent Blocks

For a data set with all missing attribute values interpreted as lost, a family $\mathcal{C}\left(B\right)$ of all maximal consistent blocks is a partition on U [18].

Properties of maximal consistent blocks for data sets with missing attribute values interpreted as “do not care” conditions were explored in [16] and other papers [22,23]. However, the estimation of the number of possible maximal consistent blocks is an open problem. In this paper, we show that such a number may exponentially grow with respect to the number of attributes.

Proposition 1.

For a data set in which all attribute values are missing and interpreted as “do not care” conditions, the total number of maximal consistent blocks is equal to 1.

Proof. 

This follows directly from the definition of maximal consistent blocks. □

Proposition 2.

For a data set with $\left|U\right|$ = 1, the total number of maximal consistent blocks is equal to 1.

Proof. 

This follows directly from the definition of maximal consistent blocks. □

In order to estimate the number of possible maximal consistent blocks for incomplete data sets with all missing attribute values interpreted as “do not care” conditions, we introduce a special data set, which we call a k-galaxy set. Let $\left|A\right|=k$, $V_a=\{1,2,\dots ,k\}$ for all $a\in A$. The set is a k-galaxy set if $a_j\left(i\right)=j$ when $k·(j-1)<i\le k·j$; otherwise, $a_j\left(i\right)=\ast$ for any $i\in \{1,2,\dots ,k^2\}$ and $j\in \{1,\dots ,k\}$. ’·’ denotes a standard arithmetic multiplication operation.

An example of a k-galaxy set (k = 3) is shown in

Table 2. An example of a k-galaxy set for k = 3.

Case	Attribute 1	Attribute 2	Attribute 3	Decision
1	1	*	*	1
2	2	*	*	1
3	3	*	*	1
4	*	1	*	2
5	*	2	*	2
6	*	3	*	2
7	*	*	1	3
8	*	*	2	3
9	*	*	3	3

.

For the k-galaxy set (k = 3) from Table 2, the set of all maximal consistent blocks of A is {{1, 4, 7}, {1, 4, 8}, {1, 4, 9}, {1, 5, 7}, {1, 5, 8}, {1, 5, 9}, {1, 6, 7}, {1, 6, 8}, {1, 6, 9}, {2, 4, 7}, {2, 4, 8}, {2, 4, 9}, {2, 5, 7}, {2, 5, 8}, {2, 5, 9}, {2, 6, 7}, {2, 6, 8}, {2, 6, 9}, {3, 4, 7}, {3, 4, 8}, {3, 4, 9}, {3, 5, 7}, {3, 5, 8}, {3, 5, 9}, {3, 6, 7}, {3, 6, 8}, {3, 6, 9}}.

For a set X, $\left|X\right|$ denotes the cardinality of X.

Lemma 1.

For a k-galaxy set, $\left|\mathcal{C}\right(\left\{a\right\}\left)\right|$ is equal to k, where $a\in A$.

Proof. 

If $a\in A$ and $V_a=\{1,2,\dots ,k\}$ then $a\left(x\right)\ne a\left(y\right)$ for any $x,y\in U$, $x\ne y$. This means that $\left\{x\right\}$ is consistent with respect to a. Therefore, from the definition of maximal consistent blocks, there are k maximal consistent blocks with respect to a. □

For instance, in Table 2, the set of maximal consistent blocks with respect to Attribute 1 from the example of a k-galaxy set for k = 3 is {{1, 4, 5, 6, 7, 8, 9}, {2, 4, 5, 6, 7, 8, 9}, {3, 4, 5, 6, 7, 8, 9}}.

Lemma 2.

For a k-galaxy set, let $j,v\in \{1,\dots ,k\}$. The set $\mathcal{C}\left(\left\{a_j\right\}\right)\left(v\right)$ is equal to $\left\{x\right|a_j\left(x\right)=v\}\cup {\bigcup }_{x=1}^{k·(j-1)}\left\{x\right\}\cup {\bigcup }_{x=k·j+1}^{k^2}\left\{x\right\}$, where $a_j\in A$.

Proof. 

Let $a\in A$, $v\in \{1,\dots ,k\}$ and $X\left(v\right)=\left\{x\right|a\left(x\right)=v\vee a\left(x\right)=\ast \}$. For any $x,y\in X\left(v\right)$, $x\ne y$, x and y are consistent with respect to a; if $a\left(x\right)=v$, then $a\left(y\right)=\ast$, so $X\left(v\right)$ is a consistent block. Moreover, there does not exist $z\in U\backslash X\left(v\right)$ such that $a\left(z\right)=v$. This means that objects with values belonging to $V_a$ are inconsistent. Therefore, $X\left(v\right)$ is a maximal consistent block with respect to the attribute a.

Any attribute of a k-galaxy set contains k inconsistent objects belonging to $V_a$ and remaining $k^2-k$ objects of the type $\left[\right(a,\ast \left)\right]$. Hence, each $\mathcal{C}\left(\right\{a\left\}\right)\left(v\right)$ includes exactly one object with a specified value v and $k^2-k$ objects $\left[\right(a,\ast \left)\right]$, and thus $\left|\mathcal{C}\right(\left\{a\right\}\left)\right(v\left)\right|$ is equal to $1+k^2-k$. □

In Lemma 3 and Proposition 3, provided below, we use Property 5 from [16] which states that the set of maximal consistent blocks can be updated sequentially depending on the currently analyzed set of attributes. Let $a,b\in B\subseteq A$, $x\in U$, $v_a,v_b\in \{1,\dots ,k\}$, $X_a\in \left\{x\right|a\left(x\right)=v_a\}$ and $X_b\in \left\{x\right|b\left(x\right)=v_b\}$, and from the definition of a k-galaxy set, $X_a\cap X_b=\varnothing$.

Lemma 3.

For a k-galaxy set, the cardinality of each maximal consistent block of $\mathcal{C}\left(B\right)$ is the same, equaling $1+k^2-k-(k-1)·\left(\right|B|-1)$, $B\subseteq A$.

Proof. 

For any $x,y\in U$, $x\ne y$, $\{x,y\}$ is consistent with respect to $\{a,b\}$ if $x\in X_a$ and $y\notin X_a$ or $y\in X_b$ and $x\notin X_b$. From Lemma 2, the $\mathcal{C}\left(\right\{a\left\}\right)$ includes exactly one object with a specified value $v_a$ and $k^2-k$ objects [(a, *)]. Thus, for $\{a,b\}$, the set of $k^2-k$ objects [(a, *)] is reduced by k objects belonging to $X_b$. Additionally, based on the construction of a k-galaxy set, the objects in $X_a$ as well as in $X_b$ are discernible, so the number of elements in $\mathcal{C}\left(\right\{a,b\left\}\right)$ is $k-1$ less than in $\mathcal{C}\left(\right\{a\left\}\right)$. Hence, increasing the number of attributes by one reduces the number of elements of $\mathcal{C}\left(B\right)$ by $k-1$. In consequence, if $B=A$, the number of elements of all $\mathcal{C}\left(B\right)$ is reduced to k. □

For instance, in Table 2, k = 3, $X_{Attribute1}=\{1,2,3\}$, $X_{Attribute2}=\{4,5,6\}$ the sets {1, 4}, {1, 5}, {1, 6}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5} and {3, 6} are consistent with respect to {Attribute1, Attribute2}, and all mentioned sets belong to R(Attribute1, Attribute2) (see Section 4). For the set $\mathcal{C}\left(\right\{Attribute1\left\}\right)$ is {{1, 4, 5, 6, 7, 8, 9}, {2, 4, 5, 6, 7, 8, 9}, {3, 4, 5, 6, 7, 8, 9}}, each block contains one object with a specified value belonging to $V_{Attribute1}$ and six objects of the type [(Attribute 1, *)], so $\left|\mathcal{C}\right(\left\{a\right\}\left)\right|=7$ (see

Table 3. Visualization of objects belonging (✓) to maximal consistent blocks with respect to Attribute 1 from the example of a k-galaxy set for k = 3.

Case	MCB${}_1$	MCB${}_2$	MCB${}_3$
1	✓
2		✓
3			✓
4	✓	✓	✓
5	✓	✓	✓
6	✓	✓	✓
7	✓	✓	✓
8	✓	✓	✓
9	✓	✓	✓

). The set $\mathcal{C}\left(\right\{Attribute1,Attribute2\left\}\right)$ is {{1, 4, 7, 8, 9} {1, 5, 7, 8, 9}, {1, 6, 7, 8, 9}, {2, 4, 7, 8, 9}, {2, 5, 7, 8, 9} {2, 6, 7, 8, 9}, {3, 4, 7, 8, 9}, {3, 5, 7, 8, 9}, {3, 6, 7, 8, 9}}, and each block contains two objects with a specified value—the first belonging to $V_{Attribute1}$ and the second belonging to $V_{Attribute2}$—and three objects [(Attribute 1, *),(Attribute 2, *)]. Therefore, $\left|\mathcal{C}\right(\{a,b\}\left)\right|=5$ (see

Table 4. Visualization of objects belonging (✓) to maximal consistent blocks with respect to Attribute 1 and Attribute 2 from the example of k-galaxy set for k = 3.

Case	MCB${}_1$	MCB${}_2$	MCB${}_3$	MCB${}_4$	MCB${}_5$	MCB${}_6$	MCB${}_7$	MCB${}_8$	MCB${}_9$
1	✓	✓	✓
2				✓	✓	✓
3							✓	✓	✓
4	✓			✓			✓
5		✓			✓			✓
6			✓			✓			✓
7	✓	✓	✓	✓	✓	✓	✓	✓	✓
8	✓	✓	✓	✓	✓	✓	✓	✓	✓
9	✓	✓	✓	✓	✓	✓	✓	✓	✓

). The number of elements in $\mathcal{C}\left(\right\{a,b\left\}\right)$ is reduced by $(k-1)$ objects with respect to $V_{Attribute2}$. Finally, each block of the $\mathcal{C}\left(A\right)$, presented above, contains three elements and is reduced again by $k-1$ objects with respect to $V_{Attribute3}$.

Proposition 3.

For a k-galaxy set $\left|\mathcal{C}\left(A\right)\right|=k^k$.

Proof. 

For any $a\in A$ from Lemma 1, $\left|\mathcal{C}\right(\left\{a\right\}\left)\right|=k$. For any $x,y\in U$, $x\ne y$, $\{x,y\}$ is consistent with respect to $\{a,b\}$ if $x\in X_a$ and $y\notin X_a$ or $x\in X_b$ and $y\notin X_b$. Additionally, based on the construction of a k-galaxy set, the objects in $X_a$ as well as in $X_b$ are discernible, so each of the k objects belonging to $X_a$ is consistent with each of the k objects belonging to $X_b$. Hence, there are $k·k$ consistent blocks with respect to the attributes {a, b}. Objects such that $\left\{x\right|a\left(x\right)=\ast andb\left(x\right)=\ast \}$ are added to every consistent block with respect to the set of attributes $\{a,b\}$. From Lemma 3, all of the blocks have the same number of elements. There are no subsets that are consistent with respect to the set of attributes $\{a,b\}$. The obtained blocks are maximal consistent blocks. Extending the set of analyzed attributes by another attribute increases the number of maximal consistent blocks k times, and thus, the number of maximal consistent blocks for the entire k-galaxy set is $k^k$. □

Therefore, in the worst case, the time complexity of computing maximal consistent blocks is $O\left(n^n\right)$, where n is the number of objects in a data set. This result indicates that the time complexity of some known algorithms for computing maximal consistent blocks was underestimated so far, and their authors suggest that the mentioned problem is associated with polynomial time complexity [22,23].

6. Parallelization of the Maximal Consistent Blocks Computations

The idea of the sequential update of the set of maximal consistent blocks based on Property 5 from [16] proposed in [25] is more effective than the commonly used method of constructing the blocks. However, the subsets merging, which removes subsets by performing comparisons between two sets (the current set of maximal consistent blocks obtained so far and the new one built for the next attribute), has a significant impact on the overall performance. Thus, the usage of maximal consistent blocks in mining real data with a large number of missing values or/and many attributes requires additional improvements. Here, a solution based on parallel processing is proposed.

Due to the fact that the subset is a transitive relation, the merge procedure can apply subset elimination in any order; in particular, merged sets of consistent blocks can be processed in pairs at the same time.

Let $A=\{a_1,\dots ,a_n\}$ and $\left|\mathcal{C}\right(\left\{a_1\right\}\left)\right|$ is equal to $k1$. Thus, the BuildProcedure splits the set of all cases U into a set of $k1$ maximal consistent blocks with respect to the first attribute (see Figure 1). Then the $k1$ blocks are divided in pairs into a batch of $(\lfloor \frac{k1}{2}\rfloor +k1mod2)$ separate tasks that are executed simultaneously. In the first batch, the BuildProcedure is called for each block of the pair and the next attribute $a_2$, then the resulting sets are merged. The ${\mathcal{C}}_1,\dots {\mathcal{C}}_{k1}$ sets of blocks, being the results of the entire batch, are divided in pairs into $(\lfloor \frac{k1}{4}\rfloor +k1mod2)$ separate merging tasks and the next batch is formed. The merging continues until a single set of $k2$ maximal consistent blocks is obtained. Then the set is divided in pairs into a batch of $(\lfloor \frac{k2}{2}\rfloor +k2mod2)$ tasks and the computations are performed for the attribute $a_3$. The processing is repeated until all the attributes in the data set are taken into account.

In the evaluation of the parallel computation, two aspects should be considered: speedup—the improvement in running time due to parallelism; and efficiency—the ratio of work done by a parallel algorithm to work done by a sequential algorithm [30]. As indicated above, in the worst case in the sequential algorithm, the time complexity of computing maximal consistent blocks is $O\left(n^n\right)$, where n is the number of objects in a data set. The proposed approach is a synchronized parallel algorithm [31]. The tasks are parallelized in batches. The results of each task from the given batch are not independent and have to be merged. This merging continues in subsequent batches of parallelized tasks until a single set of maximal consistent blocks is obtained. The processes are synchronized at the end of each batch. In the most optimistic scenario, in which all tasks in a batch are executed at the same time, the total number of batches (which can be estimated as $k/2$ for each attribute) determines the efficiency. In practice, however, the efficiency is reduced by the fact that $p-1$ processes have to wait for the processes executing the slowest task in a batch. Therefore, in the worst case, the relative improvement compared to the sequential algorithm is $O\left(n^{\frac{n}{2}}\right)$.

For the demonstration of the real values of the efficiency, the abalone data set with all missing attribute values interpreted as “do not care” conditions was selected, due to the fact that during the experiments performed, using the sequential algorithm, this set turned out to be the most demanding one [25]. The analysis was conducted using 4, 6, 8, 12, 16, 20 and 32 processors. The abalone data set contained 4177 observations and 8 attributes. The “do not care” conditions data sets were prepared by randomly replacing 5%, 10%, 15%, 20% of existing specified attribute values with the “*”s. Results of the analysis are presented in Figure 2 and Figure 3. The speedup does not increase linearly with the number of processors; instead, it tends to saturate. The efficiency drops as the number of processors increases. For parallel systems, this observation is called Amdahl’s law [32]. However, the results show a general increase in the speed (performance) of the parallel approach compared to the sequential computing of maximal consistent blocks. The proposed parallel algorithm includes operations that need to be executed sequentially and the increase in processing speed obtained due to the parallelization of the algorithm is limited by these sequential operations.

7. Conclusions

The idea of a maximal consistent block is adopted from discrete mathematics and describes the maximal collection of objects, in which all objects are similar [16]. In this paper, we prove that the total number of maximal consistent blocks for incomplete data with all missing attribute values interpreted as “do not care” conditions, in the worst case, depends exponentially on the number of attributes. More specifically, the time complexity of computing these blocks may be estimated as $O\left(n^n\right)$. The results of our work indicate that the time complexity of some known algorithms for computing maximal consistent blocks has been underestimated so far. Furthermore, taking into account the complexity of maximal consistent block calculations, adapting the implementation for parallel computing is proposed. Our experiments show an overall increase in speed (performance) of the parallel approach compared to sequential computations of maximal consistent blocks. However, due to the definition of the blocks, full parallelism does not seem possible. The proposed parallel algorithm consists of operations that must be performed sequentially—synchronized batches of parallel tasks. However, none of the algorithms for calculating maximal consistent blocks available in the literature is ready to be used in parallel computing. The presented solution is the first approach.

It is also worth mentioning that the problem of the complexity of computing maximal consistent blocks has not yet been studied in the available literature. The estimation of the worst-case of such calculations makes it possible to determine their impact on a system’s performance and indicates the upper limit of resources required in practical applications. In the future, we would like to apply this approach in the module of incomplete data mining of a fall detection system [33]. In systems based on sensors, various types of disturbances may occur, caused, for example, by power failure or battery depletion. Due to the fact that the FRSystem, created in cooperation with the Elderly Care Home in Rzeszow, is dedicated to elderly monitoring, such an extension is required.