SmartMiner: a depth first algorithm guided by tail information for mining maximal frequent itemsets

Maximal frequent itemsets (MR) are crucial to many tasks in data mining. Since the MaxMiner algorithm first introduced enumeration trees for mining MR in 1998, several methods have been proposed to use depth first search to improve performance. To further improve the performance of mining MR, we proposed a technique that takes advantage of the information gathered from previous steps to discover new MR. More specifically, our algorithm called SmartMiner gathers and passes tail information and uses a heuristic select function which uses the tail information to select the next node to explore. Compared with Mafia and GenMax, SmartMiner generates a smaller search tree, requires a smaller number of support counting, and does not require superset checking. Using the datasets Mushroom and Connect, our experimental study reveals that SmartMiner generates the same MFI as Mafia and GenMax, but yields an order of magnitude improvement in speed.