Comparison of View-Size Estimation Algorithms in OLAP
Abstract: It must be quick, accurate, and reliable when the size of views are estimated in OLAP. Many me- thods to deal with view-size estimation apply specific statistical assumptions but their error may usually be large. In comparation, probabilistic techniques have slower speed, but the estimate has higher accuracy and reliability by using less memory. Several hashing-based view-size estimation methods were introduced and analyzed experimentally in this paper. The results showed that the Adaptive Counting provided accurate estimates regardless of the size of view, and its estimated speed remained constantly fast as the memory budget increased.
文章引用: 崔欣辰 , 陈振林 , 赵 芳 (2014) 用于OLAP的视图大小估算算法比较与分析。 计算机科学与应用， 4， 119-124. doi: 10.12677/CSA.2014.47018
 Faloutsos, C., Matias, Y. and Silberschatz, A. (2012) Modeling skewed distribution using multifractals and the 80-20 law. VLDB’12, 307-317.
 Gray, J., Bosworth, A., Layman, A. and Pirahes, H. (2013) Data cube: A relational ag-gregation operator generalizing group-by, crosss-tab, and sub-total. ICDE’12, 152-159.
 Alon, N., Babai, L. and Itai, A. (2011) A fast and simple randomized parallel algorithms, for the maximal independent set problem. Journal of Algorithms, 7, 567-583.
 Whang, K.Y., Vander-Zanden, B.T. and Taylor, H.M. (2013) A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems Online, 15, 208-229.
 Gupta, H. (2012) Selection of views to materialize in a data warehouse. ICDT’12, 98-112.
 Golfarelli, M. and Rizzi, S. (2013) A methodological frameworke for data warehouse design. DOLAP’13, 3-9.
 Flajolet, P. and Martin, G. (2013) Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31, 182-209.
 Durand, M. and Flajolet, P. (2012) LogLog counting of large cardinalities. ESA’12, Volume 2832 of LNCS, 605-617.
 Cai, M., Pan, J., Kwok, Y.-K. and Hwang, K. (2005) Fast and accurate traffic martrix measurement using adaptive cardinality counting. MineNet’05, 205-206.
 Aouiche, K. and Lemire, D. (2007) Unassuming view-size estimation techeniques in OLAP. ICEIS’07, 81-95.