具有復(fù)雜約束條件的海量數(shù)據(jù)聚集及其并行化實(shí)現(xiàn).pdf

1、海量數(shù)據(jù)聚集算法是在線聯(lián)機(jī)分析處理（Online Analytical Processing，簡稱 OLAP）的核心問題。OLAP旨在處理涉及到商業(yè)智能的數(shù)據(jù)，這是一類非常重要而又異常復(fù)雜的問題。OLAP利用聚集算法產(chǎn)生的N維數(shù)據(jù)模型（數(shù)據(jù)立方體）可以在極短的時(shí)間內(nèi)響應(yīng)查詢；同時(shí)帶有復(fù)雜條件約束的范圍聚集查詢（多維范圍查詢）隨著商業(yè)智能的發(fā)展顯得越發(fā)重要。隨著計(jì)算機(jī)技術(shù)發(fā)展，查詢變得更加復(fù)雜、立方體維度不斷上升、數(shù)據(jù)規(guī)模持續(xù)擴(kuò)大，這些新

2、情況給OLAP帶來了嚴(yán)峻的挑戰(zhàn)，海量數(shù)據(jù)聚集所需的計(jì)算時(shí)間成為了嚴(yán)重制約OLAP系統(tǒng)性能的瓶頸。
　　CUDA是由NVIDIA所推出的一種集成技術(shù)，將圖形處理器（Graphic Processing Unit，GPU）引入高性能計(jì)算領(lǐng)域。同傳統(tǒng)CPU相比，GPU擁有更高的計(jì)算能力和內(nèi)部帶寬，于是如何利用GPU設(shè)計(jì)新的聚集算法成為OLAP計(jì)算領(lǐng)域中一個(gè)新的熱點(diǎn)。
　　針對利用GPU解決OLAP聚集問題，本文主要研究內(nèi)容如下：<

3、br>　?。?）分析了經(jīng)典的CPU算法和新近提出的GPU算法之間的區(qū)別及各自優(yōu)缺點(diǎn)，總結(jié)了影響聚集效率的主要因素；
　　（2）提出了一種面向并行聚集的多維前序樹（Multi-dimensionalPrefix Tree）存儲(chǔ)模型，可以依據(jù)前序編碼（Prefix Encoding）分割數(shù)據(jù)空間，對原始數(shù)據(jù)進(jìn)行壓縮和存儲(chǔ)；提出了多維前序樹并行構(gòu)造算法，并通過實(shí)驗(yàn)證明了其相對數(shù)據(jù)庫有6倍的加速比；
　　（3）基于多維前序樹模型，面