Fast Rule Mining over Multi-dimensional Windows

Association rule mining is an indispensable tool for discovering<br/>insights from large databases and data warehouses.<br/>The data in a warehouse being multi-dimensional, it is often<br/>useful to mine rules over subsets of data defined by selections<br/>over the dimensions. Such interactive rule mining<br/>over multi-dimensional query windows is difficult since rule<br/>mining is computationally expensive. Current methods using<br/>pre-computation of frequent itemsets require counting<br/>of some itemsets by revisiting the transaction database at<br/>query time, which is very expensive. We develop a method<br/>(RMW) that identifies the minimal set of itemsets to compute<br/>and store for each cell, so that rule mining over any<br/>query window may be performed without going back to the<br/>transaction database. We give formal proofs that the set of<br/>itemsets chosen by RMW is sufficient to answer any query<br/>and also prove that it is the optimal set to be computed<br/>for 1 dimensional queries. We demonstrate through an extensive<br/>empirical evaluation that RMW achieves extremely<br/>fast query response time compared to existing methods, with<br/>only moderate overhead in pre-computation and storage