摘 要：隨著計(jì)算機(jī)技術(shù)的發(fā)展，不確定數(shù)據(jù)查詢已經(jīng)受到了學(xué)術(shù)和工業(yè)界廣泛關(guān)注，成為新的研究熱點(diǎn)。本文在傳統(tǒng)的Top-k算法的基礎(chǔ)上，提出了新的RU-Topk算法，探討了在高負(fù)載的情況下，基于GPU同步模式RU-Topk查詢算法的設(shè)計(jì)實(shí)現(xiàn)，以求進(jìn)一步提高查詢效率。

關(guān)鍵詞：不確定數(shù)據(jù)；查詢算法；Top-k

中圖分類號：TP311.13

不確定數(shù)據(jù)普遍存在于天文觀測、地址測量、氣象觀測等領(lǐng)域當(dāng)中，但由于復(fù)雜的外部環(huán)境以及儀器本身精度的限制，造成采集的數(shù)據(jù)并不是準(zhǔn)確完整的[1]。隨著數(shù)據(jù)管理技術(shù)的發(fā)展，人們越來越重視不確定數(shù)據(jù)管理的問題[2]，同時(shí)各種實(shí)際需求的需要也加快了對不確定數(shù)據(jù)研究的步伐。不確定數(shù)據(jù)管理的最終目標(biāo)是對不確定數(shù)據(jù)進(jìn)行查詢處理來提高查詢的性能，最終改善用戶的體驗(yàn)效果。不確定查詢算法包括top-k查詢、輪廓查詢等方式。top-k查詢算法只查詢用戶感興趣的前k個(gè)數(shù)據(jù)，從而能夠避免返回大量的查詢的結(jié)果，因此這種查詢算法已經(jīng)在傳統(tǒng)的確定數(shù)據(jù)查詢當(dāng)中得到了大量的應(yīng)用。本文在研究top-k查詢算法的基礎(chǔ)上，對不確定數(shù)據(jù)查詢算法進(jìn)行了優(yōu)化改進(jìn)。

1 Top-k查詢

Top-k查詢的是最能夠滿足條件的k個(gè)查詢結(jié)果，如果以評分來統(tǒng)計(jì)查詢結(jié)果的話，該算法查找的就是k個(gè)值最高對象。Top-k查詢分為聚合的top-k查詢和非聚合top-k查詢兩種，其主要區(qū)別就是算法當(dāng)中是否用到了聚合函數(shù)。下圖給出了二維不確定數(shù)據(jù)top-k查詢的實(shí)例，在該圖當(dāng)中，每一個(gè)不確定的數(shù)據(jù)在它們的特征空間呈現(xiàn)一個(gè)范圍，對象的觀測值就是范圍當(dāng)中的點(diǎn)，如果用戶發(fā)出top-2查詢，那么就不能夠確定t2和t3哪一個(gè)會獲得第2高的得分，但t1明顯是得分最高的。

圖1 二維不確定數(shù)據(jù)top-k查詢實(shí)例

在日常生活當(dāng)中，人們并不關(guān)注所有的查詢結(jié)果，而是只關(guān)注滿足自己需要的一小部分結(jié)果。而Top-k查詢算法的優(yōu)點(diǎn)就類似于互聯(lián)網(wǎng)上的搜索引擎，每次進(jìn)行查詢時(shí)，對于用戶提出的查詢，都會返回最滿足查詢的前top-k個(gè)頁面，如果遇到了用戶比較感興趣的鏈接，那么查找的結(jié)果就認(rèn)為是正確的，就會去點(diǎn)擊返回的連接，如果沒有碰到感興趣的鏈接，就回去翻下一頁。因此人們很滿意這種查詢方式。

雖然top-k算法給查詢帶來了方便，但是其在查詢語義上尚存在許多不足。Top-k查詢算法根據(jù)各自的定義計(jì)算概率，最后返回概率最大的元組，并沒有向用戶提供反映其需求的指標(biāo)，用戶沒有辦法根據(jù)自己的需求過濾掉自己不感興趣的數(shù)據(jù)，查詢到自己感興趣的數(shù)據(jù)。此外，用戶雖然能夠自主設(shè)定概率閥值進(jìn)行剪枝，但是用戶很難控制集的規(guī)模，在實(shí)際的應(yīng)用當(dāng)中難度很大，造成用戶需要多次提交查詢，才能得到其想要的滿意的結(jié)果。

2 面向需求擴(kuò)展的不確定數(shù)據(jù)查詢改進(jìn)算法RU-Topk

2.1 RU-Topk算法的描述思想

RU-Topk查詢算法的主要思想表述如下：

（1）用戶可以根據(jù)自身的需求以及具體的情況來設(shè)定需求擴(kuò)展度的值，這樣可以利用該值來約束top-k查詢結(jié)果的集中，最少應(yīng)該包括了分值排名前k的元祖的個(gè)數(shù)。

（2）RU-topk的查詢的結(jié)果是由兩部分構(gòu)成，一部分來自top-k打分函數(shù)的元祖，另外的來自剩下的元祖。兩部分的查詢結(jié)構(gòu)個(gè)數(shù)總共為k個(gè)。

（3）分治的思想應(yīng)用在RU-Topk算法當(dāng)中，根據(jù)概率將第一部分k個(gè)元祖排序，先找出概率最大的i個(gè)元祖，然后做乘積，再按照概率進(jìn)行逆序，在其中加入元祖，同時(shí)求乘積。采用OptU-Topk算法計(jì)算第二部分從top-1到topk-i的值，計(jì)算過程當(dāng)中包含了從top1到topk-1的值，只不過自動舍棄了這些結(jié)果。最后合并這兩個(gè)部分對應(yīng)的矢量組。

2.2 基于圖形處理器（GPU）平臺的RU-Topk算法的設(shè)計(jì)

如果設(shè)D為可能世界空間的不確定的數(shù)據(jù)庫，設(shè)T是一個(gè)長度為k的元祖向量，該向量滿足q（T）≥qe，qe是用戶根據(jù)需求自己定義的需求擴(kuò)展閥值約束。設(shè)ΦK（W）是W中按照打分函數(shù)逆序排列得到的前k個(gè)元祖的集合；當(dāng)∣W∣

在查詢調(diào)度的時(shí)候，當(dāng)負(fù)載較高時(shí)，采用同步的模式以及批量調(diào)度查詢的方式，從而提高效率；當(dāng)負(fù)載較低時(shí)，采用異步模式。不同的狀況選擇合適的工作方式，進(jìn)一步提高查詢效率。采用同步方式來執(zhí)行RU-Topk算法的核心思想是不單獨(dú)處理某一查詢的命令，而是采用捆綁方式，形成查詢批組，然后并行執(zhí)行以提高系統(tǒng)的吞吐率。其工作原理如下圖所示：

圖2 同步模式工作圖

RU-Topk算法是基于GPU多層次的線程結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上，在多層次的掃描階段，每個(gè)線程生成迭代top-i元祖矢量，最后收集全k個(gè)線程上的結(jié)果。同步模式下，RU-Topk算法依據(jù)組的規(guī)模批量處理相應(yīng)的線程塊，并行執(zhí)行每個(gè)線程塊，在異步的模式下，僅僅需要處理一個(gè)線程塊。因?yàn)閭鹘y(tǒng)的top-k算法僅僅返回一個(gè)查詢應(yīng)答，而RU-topk返回的是滿足用戶需要的多種應(yīng)答，兩種算法所返回的信息量存在著很大的差距。對RU-topk算法的平均單位掃描時(shí)間分析表明，RU-topk算法相對應(yīng)傳統(tǒng)的top-k算法而言，其具有比較小的平均單位查詢時(shí)間，因此具有更高的效率。

3 結(jié)束語

本文優(yōu)化了現(xiàn)有的查詢語義算法，提出了能夠反映用戶需求差異化需求指標(biāo)，并且將該指標(biāo)引入了不確定查詢算法top-k，并提出新的查詢改進(jìn)算法RU-topk及其設(shè)計(jì)思想。該算法能夠使用戶更好的結(jié)合指標(biāo)值來篩選查詢的結(jié)果，更加的貼近用戶在網(wǎng)絡(luò)虛擬環(huán)境下的需求。

參考文獻(xiàn)：

[1]周傲英，金澈清，王國仁.不確定性數(shù)據(jù)管理技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009（01）：1-12.

[2]徐雪松，李玲娟，郭立瑋.基于優(yōu)化策略的不確定數(shù)據(jù)流預(yù)測方法[J].計(jì)算機(jī)工程，2011（21）：17-22.

[3]周帆，李樹全，肖春靜.不確定數(shù)據(jù)庫中概率top-k和排序查詢算法[J].計(jì)算機(jī)應(yīng)用，2010（10）：2605-2609.

[4]王爽，乇國仁.基于不確定數(shù)據(jù)的分布式Top-k查詢算法[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2010（02）：177-180.

作者簡介：吳琪（1976-），女，山西清徐人，講師，碩士，主要從事計(jì)算機(jī)應(yīng)用，信息安全。

作者單位：吉林警察學(xué)院信息工程系，長春 130117