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

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