分布式環(huán)境下ToP-K計(jì)算問(wèn)題研究.pdf

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

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

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

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

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