1 EVALUATION OF THE FREQUENTNESS PROBABIL-ACTIVE ITEMSETS QUEUE (AIQ...

7.1 Evaluation of the Frequentness Probabil-

Active Itemsets Queue (AIQ) that is initialized with all one-

item sets. The AIQ is sorted by frequentness probability

ity Calculations

in descending order. Without loss of generality, itemsets

We evaluated our frequentness probability calculation meth-

are represented in lexiographical order to avoid generating

ods on several artificial datasets with varying database sizes

them more than once. In each iteration of the algorithm,

|T | and densities. The density of an item denotes the ex-

i.e. each call of the getNext()-function, the first itemset X

pected number of transactions in which an item may be

in the queue is removed. X is the next most probable fre-

present (i.e. where its existence probability is in (0, 1]).

quent itemset because all other itemsets in the AIQ have

The probabilities themselves were drawn from a uniform

a lower frequentness probability due to the order on AIQ,

distribution. Note that the density is directly related to

and all of X’s supersets (which have not yet been gener-

the degree of uncertainty. If not stated otherwise, we used a

ated) cannot have a higher frequentness probability due to

database consisting of 10, 000 to 10, 000, 000 uncertain trans-

Lemma 17. Before X is returned to the user, it is refined

actions and a density of 0.5. The frequentness probability

in a candidate generation step. In this step, we create all

threshold τ of was set to 0.9.

supersets of X obtained by adding single items x to the end

We use the following notations for our frequentness prob-

of X, in such a way that the lexiographical order of X ∪ x

ability algorithms: Basic: basic probability computation

is maintained. These are then added to the AIQ after their

(Section 3.2), Dynamic: dynamic probability computation

respective frequentness probabilities are computed (Section

(Section 4.1), Dynamic+P: dynamic probability compu-