We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DAWN: an efficient framework of DCT for data with error estimation.
- Authors
Ming-Jyh Hsieh; Ming-Syan Chen; Philip Yu
- Abstract
Abstract On-line analytical processing (OLAP) has become an important component in most data warehouse systems and decision support systems in recent years. In order to deal with the huge amount of data, highly complex queries and increasingly strict response time requirements, approximate query processing has been deemed a viable solution. Most works in this area, however, focus on the space efficiency and are unable to provide quality-guaranteed answers to queries. To remedy this, in this paper, we propose an efficient framework of DCT for dAta With error estimatioN, called DAWN, which focuses on answering range-sum queries from compressed OP-cubes transformed by DCT. Specifically, utilizing the techniques of Geometric series and Euler’s formula, we devise a robust summation function, called the GE function, to answer range queries in constant time, regardless of the number of data cells involved. Note that the GE function can estimate the summation of cosine functions precisely; thus the quality of the answers is superior to that of previous works. Furthermore, an estimator of errors based on the Brown noise assumption (BNA) is devised to provide tight bounds for answering range-sum queries. Our experiment results show that the DAWN framework is scalable to the selectivity of queries and the available storage space. With GE functions and the BNA method, the DAWN framework not only delivers high quality answers for range-sum queries, but also leads to shorter query response time due to its effectiveness in error estimation.
- Subjects
DATA mining; OLAP technology; DATA warehousing; QUERYING (Computer science)
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2008, Vol 17, Issue 4, p683
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-006-0032-z