The discovery of association rules from large amounts of structured or semi-structured data is an important data-mining problem (Agrawal et al., 1993; Agrawal & Srikant, 1994; Braga et al., 2002, 2003; Cong et al., 2002; Miyahara et al., 2001; Termier et al., 2002; Xiao et al., 2003). It has crucial applications in decision support and marketing strategy. The most prototypical application of association rules is market-basket analysis using transaction databases from supermarkets. These databases contain sales transaction records, each of which details items bought by a customer in the transaction. Mining association rules is the process of discovering knowledge such as, 80% of customers who bought diapers also bought beer, and 35% of customers bought both diapers and beer, which can be expressed as “diaper Þ beer” (35%, 80%), where 80% is the confidence level of the rule, and 35% is the support level of the rule indicating how frequently the customers bought both diapers and beer. In general, an association rule takes the form X Þ Y (s, c), where X and Y are sets of items, and s and c are support and confidence, respectively.