| 面向不同数据分布的多维直方图算法COCA-Hist |
| |
| 引用本文： | 曹巍,王珊,覃雄派,王秋月. 面向不同数据分布的多维直方图算法COCA-Hist[J]. 计算机学报, 2008, 31(6): 1013-1024 |
| |
| 作者姓名： | 曹巍 王珊 覃雄派 王秋月 |
| |
| 作者单位： | 中国人民大学数据工程与知识工程教育部重点实验室,北京,100872 |
| |
| 基金项目： | 国家自然科学基金 , 国际合作(HP Lab)项目 |
| |
| 摘 要： | 基于代价的RDBMS优化器需要对含有范围查询的合取谓词的结果集基数进行准确的估计,多维直方图对多维数据分布进行模拟,避免在估计结果集基数时采用数据独立性假设,造成估计误差过大,进而导致选择非优化的查询执行计划.在不同的数据分布情况下,传统的多维直方图(如MHist-2)效果有很大不同.数据相关系数和值域密度、值域参数是准确刻画多维数据分布的有效指标,文中提出了根据不同的指标采用不同的动态优化的多维直方图算法COCA-Hist,可以大大改善传统多维直方图在平均情况下的准确性.通过分析传统的多维直方图的最坏情况,COCA-Hist的改进算法可以改进传统的多维直方图在最坏情况下的准确性.实验比较了COCA-Hist和传统的多维直方图MHist-2以及GENHist和STHoles的准确性和时间效率.实验显示无论在平均情况下还是在最坏情况下COCA-Hist的改进算法均优于传统的MHist-2直方图,并且COCA-Hist的准确性和创建时间均比GENHist有极大的改善,在准确性方面COCA-Hist较优于STHoles,而在空间预算有限时STHoles的创建时间比COCA-Hist高两个数量级.
|
| 关 键 词： | 多维直方图 数据相关系数 值域密度 值域参数 属性值平均跨度 |
| 修稿时间： | 2007-07-13 |
Versatile Multidimensional Histograms for Different Data Distributions |
| |
| CAO Wei,WANG Shan,QIN Xiong-Pai,WANG Qiu-Yue. Versatile Multidimensional Histograms for Different Data Distributions[J]. Chinese Journal of Computers, 2008, 31(6): 1013-1024 |
| |
| Authors: | CAO Wei WANG Shan QIN Xiong-Pai WANG Qiu-Yue |
| |
| Abstract: | |
| |
| Keywords: | multidimensional histograms data correlated coefficients value domain density value domain parameter average spread |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
