MAFIA: The Final Algorithm

PEP (Current node C, MFI) {

Expand all children using C.tail and reorder children by increasing support

Move children from C.tail to C.head with PEP pruning

HUT = C.head union C.tail;

if HUT is in the MFI

Stop searching and return

For each item i in C.tail {

newNode = C union {i}

IsHUT = whether i is the first item in the tail

if newNode is frequent

FHUT (newNode, MFI, IsHUT)

}

if (IsHUT and tail is frequent)

Stop search and go back up tree

if (C is a leaf and C.head is not in MFI)

Add C.head to MFI

}

PEP

HUTMFI

FHUT