用于OLAP的视图大小估算算法比较与分析

Comparison of View-Size Estimation Algorithms in OLAP

摘要: OLAP系统中的视图物化操作，要求快速、可靠而精确。许多视图大小估算技术利用特定的统计假设，其误差可能较大。基于概率的估算方法在速度方面可能较慢，但是在估算大视图时精确度和可靠度较高，而且使用内存较少。论文中介绍了几种基于散列的视图大小估算方法，并进行了实验加以分析对比。实验结果表明，修正算法(Adaptive Counting)不管视图大小如何均提供精确的估算，而且当增大存储预算时仍可保持较快的估算速度。

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.