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

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

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

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

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