DAWN: an efficient framework of DCT for data with error estimation

✍ Scribed by Ming-Jyh Hsieh; Wei-Guang Teng; Ming-Syan Chen; Philip S. Yu

• Book ID: 106234689
• Publisher: Springer-Verlag
• Year: 2006
• Tongue: English
• Weight: 454 KB
• Volume: 17
• Category: Article
• ISSN: 1066-8888
• DOI: 10.1007/s00778-006-0032-z

✦ Synopsis

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 pro-