Approximate Query Processing in Cube Streams
Journal
IEEE Transactions on Knowledge and Data Engineering
Journal Volume
19
Journal Issue
11
Pages
1557-1570
Date Issued
2007
Date
2007
Author(s)
Abstract
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. © 2007 IEEE.
Subjects
Cube streams; Data cubes; Data streams; OLAP
SDGs
Other Subjects
Cube streams; Data cubes; Data streams; OLAP; Approximation theory; Constraint theory; Data structures; Information systems; Resource allocation; Query processing
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
58.pdf
Size
2.54 MB
Format
Adobe PDF
Checksum
(MD5):4fa76feb50bd18f98795d717d028c1a6