Data cubes have become important components in most data warehouse systems and decision support systems. In such systems, users usually pose very complex queries to the online analytical processing (OLAP) system, and systems usually have to deal with a huge amount of data because of the large dimensionality of the sets; thus, approximating query processing has emerged as a viable solution. Specifically, the applications of cube streams handle multidimensional data sets in a continuous manner in contrast to the traditional cube approximation. Such an application collects data events for cube streams online, generates snapshots with limited resources, and keeps the approximated information in a synopsis memory for further analysis. Compared to the OLAP applications, applications of cube streams are subject to many more resource constraints on both the processing time and the memory and cannot be dealt with by existing methods due to the limited resources. In this paper, we propose the DAWA algorithm, which is a hybrid algorithm of discrete cosine transform (DCT) for data and the discrete wavelet transform (DWT), to approximate cube streams. Our algorithm combines the advantages of the high compression rate of DWT and the low memory cost of DCT. Consequently, DAWA requires much smaller working buffer and outperforms both DWT-based and DCT-based methods in execution efficiency. Also, it is shown that DAWA provides a good solution for an approximate query processing of cube streams with a small working buffer and a short execution time. The optimality of the DAWA algorithm is theoretically proved and empirically demonstrated by our experiments.

For time-relevant multi-dimensional data sets (MDS), users usually pose a huge amount of data due to the large dimensionality, and approximating query processing has emerged as a viable solution. Specifically, the cube streams handle MDSs in a continuous manner. Traditional cube approximation focuses on generating single snapshots rather than continuous ones. To address this issue, the application of generating snapshots for cube streams, called SCS, is investigated in this paper. Such an application collects data events for cube streams on-line and generates snapshots with limited resources in order to keep the approximated information in synopsis memory for further analysis. As compared to OLAP applications, the SCS ones are subject to much more resource constraints for both processing time and memory and cannot be dealt with by existing methods due to the limited resources. In this paper, the DAWA algorithm, standing for a hybrid algorithm of Dct for Data and discrete WAvelet transform, is proposed to approximate the cube streams. The DAWA algorithm combines the advantage of high compression rate from DWT and that of low memory cost from DCT. Consequently, DAWA costs much smaller working buffer and outperforms both DWT-based and DCT-based methods in execution efficiency. Also, it is shown that DAWA provides answers of good quality for SCS applications with a small working buffer and short execution time. The optimality of algorithm DAWA is theoretically proved and also empirically demonstrated by our experiments.

In this paper a new mining capability, called mining of substitution rules, is explored. A substitution refers to the choice made by a customer to replace the purchase of items with that of others. The process of mining substitution rules can be decomposed into two procedures. The first identifies concrete itemsets among a large number of frequent itemsets, where a concrete itemset is a frequent itemset whose items are statistically dependent. The second is substitution rule generation. Two concrete itemsets X and Y form a substitution rule, denoted by X /spl utri/ Y to mean that X is a substitute for Y if and only if X and Y are negatively correlated and the negative association rule X /spl rarr/ Y~ exists. We derive theoretical properties for the model of substitution rule mining. Then, in light of these properties, the SRM algorithm (substitution rule mining) is designed and implemented to discover substitution rules efficiently while attaining good statistical significance. Empirical studies are performed to evaluate the performance of the SRM algorithm. It is shown that SRM produces substitution rules of very high quality.