不確定數(shù)據(jù)查詢及優(yōu)化技術(shù)研究.pdf

1、不確定數(shù)據(jù)廣泛存在于文本分析、信息檢索、傳感器網(wǎng)絡(luò)和射頻識別等領(lǐng)域中。隨著數(shù)據(jù)采集手段的發(fā)展,客觀世界中普遍存在的數(shù)據(jù)不確定性已經(jīng)逐漸被人們所認(rèn)識。不確定數(shù)據(jù)查詢處理問題已經(jīng)引發(fā)了學(xué)術(shù)界和工業(yè)界的共同關(guān)注與重視,成為新近發(fā)展起來的研究熱點(diǎn)。
　　 Top-k查詢方法應(yīng)用十分廣泛。在傳統(tǒng)確定數(shù)據(jù)處理中,top-k查詢只需要返回打分函數(shù)值最大的k個數(shù)據(jù)對象,而對于不確定數(shù)據(jù)top-k查詢,由于概率的存在,打分函數(shù)與概率的相互作用決定

2、返回的查詢結(jié)果,考量二者不同的結(jié)合方式則產(chǎn)生不同的不確定top-k查詢語義。但在已有的不確定數(shù)據(jù)top-k查詢語義中,只返回在可能世界中聚集概率最大的一個應(yīng)答,并不能滿足用戶差異化的查詢需求。針對這個問題,本文引入了反映查詢需求的指標(biāo)——需求擴(kuò)展度,定義了基于需求擴(kuò)展的不確定數(shù)據(jù)查詢語義RU-Topk,并且提出了在新的語義下的查詢算法,實(shí)驗(yàn)表明RU-Topk算法具有較小的平均單位查詢運(yùn)行時(shí)間,在滿足用戶需求的情況下,具備更高的查詢效率。

3、
　　 由于概率維的存在,不確定數(shù)據(jù)top-k查詢需要在與元組個數(shù)呈指數(shù)規(guī)模增長的可能世界空間中進(jìn)行掃描。本文探討了基于圖形處理器(Graphic Processing Unit,GPU)的并行計(jì)算技術(shù)進(jìn)行RU-Topk算法優(yōu)化的方法。GPU由于其多核、多線程、高帶寬、計(jì)算能力強(qiáng)等高性能特點(diǎn),使得近年基于GPU的通用并行計(jì)算得到廣泛應(yīng)用。本文根據(jù)RU-Topk語義下算法的特點(diǎn),探討了在查詢?nèi)蝿?wù)高負(fù)載情況下,基于GPU同步模式的R