Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries

of {A, B, C, D} contain items that can be used to form rules with zero or one exception (e.g., A, B ! C for {A, B, C}, B, D ! A for {A, B, D}, A, C ! D for {A, C, D}, B, C ! D for {B, C, D}, and A, B, [...] rule A, B ! C nearly holds in r (i.e., when A and B are true in a row then, excepted in a few cases, C is also true) then we can approximate the support of itemset {A, B, C} using the support of {A, B} [...] the rule A, B ! C has only one ex- ception. So, we can use the support of {A, B} as a value for the support of {A, B, C}. Moreover, we can approximate the support of any itemset X such that {A, B, C} " X …

+ r(aI + bI)r−1 ) (aI + bI)r ((aI + bI)r + (aI + bI)r)2 V − ((r + 1)(aI + bI)r(aI + bI)r) ( (aI + bI)r + (aI + bI)r )2 ((aI + bI)r + (aI + bI)r)4 rV − (r(aI + bI)r−1(aI + bI)r+1) ( (aI + bI)r + (aI + bI)r [...] bI)r )2 ((aI + bI)r + (aI + bI)r)4 rV + 2 ( (aI + bI)r ) ( r(aI + bI)r−1 + r(aI + bI)r−1 ) (aI + bI)r+1(aI + bI)r ((aI + bI)r + (aI + bI)r)4 rV + 2(aI + bI)r ( r(aI + bI)r−1 + r(aI + bI)r−1 ) (aI + bI)r+1(aI [...] r(aI + bI)r−1 ( (aI + bI)r + (aI + bI)r ) ((aI + bI)r + (aI + bI)r)2 I2V − ( r(aI + bI)r−1 + r(aI + bI)r−1 ) (aI + bI)r ((aI + bI)r + (aI + bI)r)2 I2V + (r(aI + bI)r−1(aI + bI)r+1) ( (aI + bI)r + (aI + …