Adtrees for fast counting and fast learning of association rules

The problem of discovering association rules in large data-bases has received considerable research attention. Much research has examined the exhaustive discovery of all asso-ciation rules involving positive binary literals (e.g. Agrawal et al. 1996). Other research has concerned finding complex association rules for high-a&y attributes such as CN2 (Clark and Niblett 1989). Complex association rules are ca-pable of representing concepts such as “Purchased-Chips=Tme and PnrchasedSoda=False and Area=NorthEast and CustomerType=Occasional * AgeRange=Young”, but their generality comes with severe computational penalties (intractable numbers of preconditions can have large sup-port). Here, we introduce new algorithms by which a sparse data structure called the ADtree, introduced in (Moore an