%A WU Zhenpeng, ZHANG Jian, FAN Xingqi, LI Cuiping
%T Median calculation algorithms based on GPU in OLAP
%0 Journal Article
%D 2021
%J Journal of Shandong University(Engineering Science)
%R 10.6040/j.issn.1672-3961.0.2019.508
%P 7-14
%V 51
%N 3
%U {http://gxbwk.njournal.sdu.edu.cn/CN/abstract/article_2032.shtml}
%8 2021-06-20
%X An algorithm for one of the holistic aggregate operations in online analytical processing(OLAP)called Median was proposed based on graphics processing unit(GPU), which was named GPU-Median algorithm. This algorithm obtained the median of a series of data by segmenting the data, sorting the data by segments,cutting the data preceding the global median, and finally merging the uncut data. Through the algorithm above much time spent on global sorting was saved. Then an algorithm called GPU-Median+was presented in order to optimize and extend the GPU-Median algorithm. This algorithm implemented the aggregate operations through the collaboration of CPU and GPU, which used GPU to deal with segments of data and CPU to deal with global data. Experiments and analysis proved that the GPU-Median + algorithm reduced the time complexity of the median calculation from O(n^{2})to O(n)compared to the CPU algorithm,and that the GPU-Median + algorithm reduced a third of the calculation time compared to the radix sort algorithm on the GPU. The application of this algorithm enabled the GPU to improve its ability of parallel calculations when calculating the holistic aggregate function in OLAP, thus providing a new idea for improving the query performance of OLAP.