由贪心策略构造Chebyshev多项式概要

摘要：

基于Chebyshev多项式的概要能有效估计数据库关系属性的频度分布.然而,从M个Chebyshev系数选择最近似原始频度分布的N(N<M)个系数,是NP难问题.依据贪心策略,提出了三种概要构造算法,精度最高的一个称为GreedyB. GreedyB先找出2N个绝对值最大的系数,再由贪心策略剔除多余的N个.在模拟数据序列和实际数据序列的实验数据表明,GreedyB尽管时间复杂度要高,但L1、L2、L∞等误差显著较小.

关键词：贪心策略、Chebyshev多项式、概要、数据库关系属性、频度分布

所属期刊栏目：29

分类号：TP18;TP301.6(自动化基础理论)

资助基金：国家自然科学基金资助项目60873016

在线出版日期：2009-08-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：2253-2256