MapReduce框架下Skyline查詢算法研究與改進(jìn).pdf

1、隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)規(guī)模和種類急劇增大，如何在海量數(shù)據(jù)中找出對(duì)用戶有用的信息至關(guān)重要。Skyline查詢作為經(jīng)典的查詢算法，能夠有效返回原始數(shù)據(jù)集上的一組較優(yōu)子集，將Skyline算法應(yīng)用到MapReduce并行計(jì)算框架，成為處理大數(shù)據(jù)環(huán)境下Skyline查詢的有效方法。高維度、大數(shù)據(jù)集上Skyline查詢算法的時(shí)空開(kāi)銷大，因此如何提高大數(shù)據(jù)下的Skyline算法效率成為一個(gè)研究熱點(diǎn)。由于Skyline結(jié)果集規(guī)模隨維度呈指數(shù)級(jí)增長(zhǎng)

2、，大數(shù)據(jù)環(huán)境下Skyline結(jié)果集規(guī)模巨大從而無(wú)法為用戶返回精準(zhǔn)的信息，如何選取規(guī)模更小、更具有代表性的查詢結(jié)果值得進(jìn)一步研究。
　　針對(duì)大數(shù)據(jù)環(huán)境下Skyline查詢效率低問(wèn)題，提出了一種基于MapReduce框架的廣義支配優(yōu)化Skyline查詢算法。該算法定義了全空間廣義支配的概念，驗(yàn)證了廣義支配的快速性和高效性，利用廣義支配過(guò)濾原始數(shù)據(jù)集中的非Skyline點(diǎn)從而為Skyline查詢提供削減的數(shù)據(jù)集。通過(guò)優(yōu)化數(shù)據(jù)點(diǎn)支配能力的

3、計(jì)算方法，利用MapReduce復(fù)合鍵值對(duì)削減后的數(shù)據(jù)集按照支配能力大小排序，以加快非Skyline點(diǎn)的過(guò)濾。實(shí)驗(yàn)結(jié)果表明，該算法可以有效加快非Skyline點(diǎn)的過(guò)濾，提高Skyline查詢算法的時(shí)間性能。
　　針對(duì)大數(shù)據(jù)環(huán)境下Skyline結(jié)果集規(guī)模巨大問(wèn)題，為了對(duì)Skyline結(jié)果集進(jìn)行優(yōu)選、得到更具有代表性的Skyline結(jié)果，提出了MapReduce框架下基于支配個(gè)數(shù)的Skyline結(jié)果集優(yōu)化算法。該算法提出了數(shù)據(jù)點(diǎn)支配個(gè)