分布式數(shù)據(jù)的反SKYLINE查詢算法研究.pdf

1、反skyline查詢常用在數(shù)據(jù)挖掘和決策支持系統(tǒng)中，用于數(shù)據(jù)的多準則優(yōu)化。但目前有關(guān)反skyline查詢的研究僅限于集中式數(shù)據(jù)，分布式數(shù)據(jù)上的反skyline查詢尚未有文獻涉及。在現(xiàn)實應(yīng)用中，基于更新成本、性能等考慮，數(shù)據(jù)經(jīng)常是分散存放并通過網(wǎng)絡(luò)互連的，現(xiàn)有的集中式算法無法滿足分布式環(huán)境。本文將分布式數(shù)據(jù)上的反skyline查詢作為研究重點，具體工作包括以下幾個方面：
　?。?）分析當前集中式數(shù)據(jù)集上的反skyline查詢方法，設(shè)

2、計了分布式數(shù)據(jù)集上的反skyline查詢算法BBDRS。遠程站點利用R樹索引預(yù)計算反skyline點集的候選集和篩選集，并將其作為發(fā)往中央站點的數(shù)據(jù)摘要，一方面降低了總體反應(yīng)延遲，另一方面避免發(fā)送全部數(shù)據(jù)，減少了大量的通信開銷。
　　（2）針對上述R樹算法花費大量時間建立索引的問題，設(shè)計了分布式數(shù)據(jù)集上一種使用預(yù)排序的反skyline查詢算法PDRS。該算法采用上述相同的通信策略，核心思想是將各數(shù)據(jù)點按與查詢點的”距離”進行預(yù)排序

3、，在避免建立索引的同時大大減少支配比較次數(shù)，節(jié)省了計算時間。在非很大規(guī)模數(shù)據(jù)上，PDRS性能較BBDRS好。
　　（3）借鑒當前單數(shù)據(jù)流上的反skyline查詢方法，設(shè)計了分布式數(shù)據(jù)流上的反skyline查詢算法—DCDRS算法。客戶端，利用DC樹索引實時計算和維護當前窗口內(nèi)最新的數(shù)據(jù)摘要信息；服務(wù)器端，則利用集中式算法計算最終結(jié)果。DCDRS算法能夠正確并有效的解決分布式數(shù)據(jù)流環(huán)境下的反skyline查詢問題。
　?。?）