1、近年來(lái)，隨著互聯(lián)網(wǎng)應(yīng)用的迅速發(fā)展和云計(jì)算技術(shù)的廣泛應(yīng)用，數(shù)據(jù)存儲(chǔ)量呈現(xiàn)爆炸式增長(zhǎng)。如何在大規(guī)模數(shù)據(jù)集中找到人們感興趣的數(shù)據(jù)，幫助人們做出有效的決斷，是一個(gè)亟待解決的問(wèn)題。Skyline計(jì)算用于解決多目標(biāo)決策問(wèn)題。從已有的研究?jī)?nèi)容來(lái)看，Skyline計(jì)算可分為集中式處理和分布式處理。集中式處理的研究相對(duì)較為成熟，包括BNL(blocknestedloop)、D&C(divideandconquer)和SFS(sort-filter-sky

2、line)等多種算法。由于大數(shù)據(jù)的發(fā)展，分布式處理尤為重要。MapReduce模型由Google公司提出，該模型具有高容錯(cuò)性和良好的擴(kuò)展性，適用于數(shù)據(jù)密集型應(yīng)用處理。因此，將Skyline計(jì)算置于MapReduce模型下運(yùn)行是一個(gè)很好的選擇。
　　Skyline計(jì)算在MapReduce模型上運(yùn)行，需要考慮的問(wèn)題是如何對(duì)數(shù)據(jù)集進(jìn)行劃分。目前已知的劃分方法有隨機(jī)劃分、網(wǎng)格劃分和基于角度的劃分。隨機(jī)劃分簡(jiǎn)單，但是運(yùn)行不穩(wěn)定。網(wǎng)格劃分僅適

3、用于低維度數(shù)據(jù)集。基于角度的劃分先將點(diǎn)的坐標(biāo)投影到超球面上，然后根據(jù)超球面坐標(biāo)對(duì)數(shù)據(jù)集進(jìn)行劃分。使用這種劃分在求局部結(jié)果集時(shí)可以淘汰更多數(shù)據(jù)，但該劃分前的坐標(biāo)轉(zhuǎn)換較復(fù)雜、費(fèi)時(shí)。本文采用基于超平面投影的劃分對(duì)數(shù)據(jù)集進(jìn)行劃分。該劃分首先將點(diǎn)的坐標(biāo)投影到超平面上，然后根據(jù)超平面坐標(biāo)對(duì)數(shù)據(jù)集進(jìn)行劃分。這種劃分方法繼承了基于角度劃分的優(yōu)點(diǎn)，即劃分后求出的局部結(jié)果集較小，同時(shí)彌補(bǔ)了基于角度劃分的不足，即該劃分前的坐標(biāo)轉(zhuǎn)換簡(jiǎn)單、省時(shí)。本文提出基于該劃