关键词: 贪心策略, Chebyshev多项式, 概要, 数据库关系属性, 频度分布, greedy strategy, Chebyshev polynomial, synopsis, database relation attribute, frequency distribution

Abstract: The synopses based Chebyshev polynomials can be efficiently used to estimate frequency distribution of attributes of a given database relation. However, it is a NPhard problem to choose N coefficients most approximate to the origin frequency distribution from M (M>N)Chebyshev polynomial coefficients. Three greedy algorithms were introduced, and the best one was named GreedyB. First, 2N largest absolute value coefficients were picked out, then, redundant N coefficients were eliminated by greedy strategy. Experimental results over synthetic and real data sequences clearly show that compared with the existing algorithms, despite GreedyB has higher time complexity, it achieves higher accuracy as measured by the L1,L2 and L_inf error metrics.