关键词: 星型模型, 百分点, 并行算法, 迭代

Abstract: This paper proposes a parallel percentile computing algorithm over flattening encoded star schema. Firstlyhierarchies of all dimensions pertaining to queries in a star schema are encoded into the fact table, the encodingscheme enables processing queries without joining between the fact table and dimension tables after query rewriting,thus data can be partitioned onto a large cluster evenly, and high performance is achieved through parallel processing.Percentile computing is not naturally parallelizable, this paper also puts forward an iterative parallel algorithm based on prediction. Through paying out the cost of data sampling, the algorithm converges quickly, and resolves the problem of computing percentile on a large scale cluster. Experiment results demonstrate that not only the algorithm converges quickly, but also the network overhead is acceptable.

Key words: star schema, percentile, parallel algorithm, iterative