基于MapReduce的海量Skyline計算研究.pdf

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

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

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