1、Top-k計算作為一種偏好查詢，是數(shù)據(jù)庫中一個最基本的操作，旨在從給定的數(shù)據(jù)集中查找出用戶可能感興趣的信息。作為一種數(shù)據(jù)分析的重要工具，top-k計算在網(wǎng)頁搜索、電子商務(wù)、數(shù)據(jù)挖掘、多標(biāo)準(zhǔn)決策支持等領(lǐng)域有著廣泛的應(yīng)用。隨著大數(shù)據(jù)時代的來臨，傳統(tǒng)的top-k處理技術(shù)遇到前所未有的挑戰(zhàn)，已經(jīng)無法滿足大數(shù)據(jù)分析的需求。新環(huán)境下的top-k計算主要面臨著三個挑戰(zhàn):一是數(shù)據(jù)規(guī)模達(dá)到TB或者PB級，傳統(tǒng)的單機處理方式不再適用，應(yīng)該考慮分布式并行計算

2、框架;二是對于面對海量數(shù)據(jù)集，在分布式環(huán)境下，采取怎樣的數(shù)據(jù)劃分方法才能夠提升并行性能和查詢速度;三是傳統(tǒng)的top-k查詢需要用戶給定一個評分函數(shù)，而選擇一個合適的評分函數(shù)卻不是件容易的事。
　　因此，本文對分布式環(huán)境下top-k計算的數(shù)據(jù)劃分和并行算法設(shè)計的關(guān)鍵技術(shù)進(jìn)行了研究和探索，主要的研究內(nèi)容包括:
　　(1)在分布式計算框架下，針對于加權(quán)top-k查詢問題，提出了類似網(wǎng)格數(shù)據(jù)劃分方式，將原始數(shù)據(jù)集劃分為不同的子數(shù)據(jù)集

3、，根據(jù)用戶偏好選取子數(shù)據(jù)集代替全部數(shù)據(jù)集進(jìn)行查詢，減少查詢數(shù)據(jù)。針對于高維度中的“空空間”現(xiàn)象，本文在網(wǎng)格劃分基礎(chǔ)上引入超平面劃分。與基于角度和超平面的數(shù)據(jù)劃分方式相比，該方法預(yù)處理簡單不用進(jìn)行復(fù)雜坐標(biāo)轉(zhuǎn)換，而且對于較高維度中出現(xiàn)的“空空間”現(xiàn)象依舊適用。實驗結(jié)果證明在大數(shù)據(jù)環(huán)境下類似網(wǎng)格和超平面數(shù)據(jù)劃分方法查詢速度比基于角度劃分方法快了接近15％，此外對于數(shù)據(jù)維度較高時候出現(xiàn)的“空空間”現(xiàn)象(實驗中即:d大于等于8)，比基于角度劃分方

4、法，查詢結(jié)果更準(zhǔn)確，同時具有良好的可擴(kuò)展性。
　　(2)針對于傳統(tǒng)的top-k查詢需要用戶給定一個評分函數(shù)，而某些用戶難以給出一個合理的評分函數(shù)這一問題。在結(jié)合已有的單機算法基礎(chǔ)上提出了五種在分布式平臺下基于度量空間的并行top-k dominating查詢算法。算法1利用skyline集合中一定包含top-1 dominating結(jié)果這一結(jié)論，分區(qū)并行計算skyline，來加快處理速度;同時利用候選集的支配關(guān)系，避免k次重復(fù)計算

5、。算法2利用k-skyband集合中包含所有top-kdominating結(jié)果這一結(jié)論，每個分區(qū)并行計算k-skyband，避免k次循環(huán)。算法3在算法1基礎(chǔ)上，首先結(jié)合ANN對原始數(shù)據(jù)進(jìn)行篩選，加快對skyline的計算。算法4為一種基于集合ANN和k-skyband的剪枝算法，該算法利用集合ANN預(yù)先剪枝，再求k-skyband，最后獲取top-k dominating，加快計算k-skyband速度。算法5為一種基于排序剪枝的top