分布式數(shù)據(jù)流上基于K-Skyband的Top-K支配查詢研究.pdf

1、Top-K支配查詢返回數(shù)據(jù)集中支配其它數(shù)據(jù)點個數(shù)最多的前K個點，它繼承了Skyline查詢和Top-K查詢的優(yōu)點而避免了二者的缺點，在偏好搜索、多標(biāo)準(zhǔn)決策支持等領(lǐng)域具有重要作用。目前關(guān)于Top-K支配查詢的研究局限于集中式數(shù)據(jù)集。然而，在金融信息分析、傳感器網(wǎng)絡(luò)等新興應(yīng)用領(lǐng)域，數(shù)據(jù)從地理上分布的不同數(shù)據(jù)源以流的形式連續(xù)地傳送到中央數(shù)據(jù)倉庫的特征日益顯現(xiàn)。如何從這些分布的、流動的海量數(shù)據(jù)中實時地挖掘到有用信息是近年來流數(shù)據(jù)挖掘領(lǐng)域中的研究

2、熱點。本文將分布式數(shù)據(jù)流上Top-K支配查詢作為研究重點，具體工作包括以下幾個方面：
　?。?）發(fā)現(xiàn)Top-K支配查詢結(jié)果是K-Skyband查詢結(jié)果的子集，并以此提出通過預(yù)先維護(hù)分布式數(shù)據(jù)流上的K-Skyband來進(jìn)一步求解Top-K支配查詢結(jié)果的思想。
　　（2）本文基于網(wǎng)格索引提出一種分布式數(shù)據(jù)流上連續(xù)K-Skyband查詢算法GBIFA。GBIFA通過傳送K-Skyband增量來減少站點間通信開銷。此外，GBIFA對

3、網(wǎng)格索引進(jìn)行支配區(qū)域劃分，避免了更新時大量的支配測試，減少了時間開銷。
　?。?）本文實現(xiàn)了一種基于K-Skyband的分布式數(shù)據(jù)流上連續(xù)Top-K支配查詢算法GKTDM。圍繞減少時間開銷為目的，該算法將K-Skyband作為Top-K支配查詢結(jié)果的候選集，只對K-Skyband點而非全部數(shù)據(jù)計算支配能力；此外，提出保留支配能力的思想，避免更新后重新計算K-Skyband點的支配能力；最后，采用遠(yuǎn)程站點預(yù)先判定新數(shù)據(jù)身份的策略，避

4、免中央站點在接收到局部站點的候選K-Skyband點時也對全局K-Skyband集合進(jìn)行更新維護(hù)。
　?。?）本文以多線程服務(wù)器/客戶機(jī)模型模擬分布式數(shù)據(jù)流環(huán)境，設(shè)計了一個分布式數(shù)據(jù)流查詢實驗平臺，可以高效和自動地測試所提算法在不同參數(shù)下的性能。
　　本文對分布式數(shù)據(jù)流上Top-K支配查詢的研究，在偏好搜索、多標(biāo)準(zhǔn)決策支持等領(lǐng)域具有重要的現(xiàn)實意義。在分布式數(shù)據(jù)流上的數(shù)據(jù)挖掘越來越受關(guān)注的今天，本文的工作可以促進(jìn)Top-K支配