{"title":"Approximate Range-Sum Queries over Data Cubes Using Cosine Transform","authors":"Wen-Chi Hou, Cheng Luo, Zhewei Jiang, Feng Yan","volume":24,"journal":"International Journal of Computer and Information Engineering","pagesStart":4217,"pagesEnd":4224,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/3028","abstract":"In this research, we propose to use the discrete cosine\r\ntransform to approximate the cumulative distributions of data cube\r\ncells- values. The cosine transform is known to have a good energy\r\ncompaction property and thus can approximate data distribution\r\nfunctions easily with small number of coefficients. The derived\r\nestimator is accurate and easy to update. We perform experiments to\r\ncompare its performance with a well-known technique - the (Haar)\r\nwavelet. The experimental results show that the cosine transform\r\nperforms much better than the wavelet in estimation accuracy, speed,\r\nspace efficiency, and update easiness.","references":"[1] W. Acharya and P. Gibbons and V. Poosala, Aqua: A Fast Decision\r\nSupport System Using Approximate Query Answers, 1999, Proc. 25th\r\nVLDB Conference.\r\n[2] D. Barbara and M. Sullivan, Quasi-cubes: Exploiting approximation in\r\nmulti-dimensional databases, 1997, SIGMOD Record, 26, 12-17.\r\n[3] C. Chan and Y. Ioannidis, Hierarchical cubes for range-sum queries,\r\n1999, Proc. VLDB, 675-686.\r\n[4] S. Geffner and D. Agrawal and A. Abbadi and T. Smith, Relative prefix\r\nsums: an efficient approach for querying dynamic OLAP Data Cubes,\r\n1999, Proc. ICDE, 328-335.\r\n[5] S. Geffner and D. Agrawal and A. Abbadi, The dynamic data cubes,\r\n2000, Proceeding of International Conference on Extending Database\r\nTechnology (EDBT), 237-253.\r\n[6] J. Gray and A. Bosworth and A. Layman and H. Pirahesh, Data cube:\r\nA relational aggregation operator generalizing group-by, cross-tab, and\r\nsub-totals, 1996, Proc. ICDE Conference.\r\n[7] C. Ho and R. Agrawal and N. Megiddo and R. Srikant, Range queries\r\nin OLAP data cubes, 1997, Proc. ACM SIGMOD Conference, 73-88.\r\n[8] L. Lakshmanan and J. Pei and J. Han, Quotient cube: How to summarize\r\nthe semantics of a data cube, 2002, Proc. 28th VLDB Conference, 528-\r\n539.\r\n[9] J. Lee and D. Kim and C. Chung, Multi-dimensional Selectivity Estimation\r\nUsing Compressed Histogram Information, 1999, ACM SIGMOD,\r\n205-214.\r\n[10] S. Li and S. Wang, Semi-closed cube: An effective approach to trading\r\noff data cube size and query response time, Journal of Computer Science\r\nand Technology, 20(3), 367-372.\r\n[11] Y. Matias and J. Vitter and M. Wang, Wavelet-based histograms for\r\nselectivity estimation, 1998, ACM SIGMOD Conference, 448-459.\r\n[12] Y. Matias and J. Vitter and M. Wang, Dynamic Maintenance of Wavelet-\r\nBased Histograms, 2000, Proc 26th VLDB Conference, 101-110.\r\n[13] Y. Nievergelt, Wavelets Made Easy, 1999, Birkhauser.\r\n[14] Y. Sismanis and N. Roussoupoulos and A. Deligiannakis and Y. Kotidis,\r\nDwarf: Shrinking the petacube, 2002, Proc. ACM SIGMOD Conference,\r\n464-475.\r\n[15] J. Vitter and M. Wang and B. Lyer, Data cube approximation and\r\nhistograms via wavelets, 1998, Proc. CIKM, 96-104.\r\n[16] W. Wang and J. L. Feng, Condensed cube: An effective approach to\r\nreducing data cube size, 2002, Proceedings of the 18th International\r\nConference on Data Engineering.\r\n[17] G. Zipf, Human behavior and the principle of least effort, 1949, Addison-\r\nWesley.\r\n[18] TPC, TPC benchmark D, decision support, 1995.\r\n[19] BC, http:\/\/www.bls.census.gov\/sipp\/ ftp.html#sipp04, 2004.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 24, 2008"}