基于參數(shù)化排序的不確定Top-k查詢算法

鄒志文，張 翅

(江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013)

移動物體跟蹤[1]、RFID技術(shù)、傳感器網(wǎng)絡(luò)和數(shù)據(jù)融合等應(yīng)用中產(chǎn)生海量數(shù)據(jù)，如何從這些海量數(shù)據(jù)中選擇最符合查詢條件的信息是數(shù)據(jù)管理的一個重要課題[2].在數(shù)據(jù)產(chǎn)生過程中，由于原始數(shù)據(jù)不準(zhǔn)確、需要處理缺失值，滿足特殊需求應(yīng)用，以及使用粗粒度數(shù)據(jù)集合還有數(shù)據(jù)的集成等眾多原因[3]，會產(chǎn)生海量的不確定數(shù)據(jù).不確定數(shù)據(jù)的管理已經(jīng)成為數(shù)據(jù)庫研究領(lǐng)域的熱點(diǎn)之一.

Top-k查詢是數(shù)據(jù)庫管理的重要應(yīng)用之一[4].當(dāng)數(shù)據(jù)由確定性數(shù)據(jù)轉(zhuǎn)換為不確定性數(shù)據(jù)時會對查詢結(jié)果產(chǎn)生很大影響，甚至?xí)淖兿鄳?yīng)的查詢語義[5].當(dāng)前不確定數(shù)據(jù)庫的Top-k查詢算法已經(jīng)有很多種.如U-Topk[6]返回在所有可能世界中具有最大概率的k個元組，U-kRanks[7]返回k個元組的列表，使得第i個排名的元組在所有的可能世界中具有最高的聚合概率.而這兩種查詢算法，由于缺少相應(yīng)的剪枝方法從而增加了需要搜索的可能世界實(shí)例的數(shù)量，所以導(dǎo)致了效率低下.而PT-k查詢返回的是所有可能世界中Top-k概率不低于給定概率閾值的元組集合，使得在不展開可能世界的前提下，提高算法的性能.參數(shù)化排序中的E-score[8]查詢語義返回數(shù)據(jù)概率和屬性分值乘積最大的前k個數(shù)據(jù)，由于缺少相應(yīng)的剪枝方法，E-score算法的效率同樣不高.

文中提出基于參數(shù)化排序的ETK查詢算法，在對數(shù)據(jù)進(jìn)行剪枝后，引用一個動態(tài)規(guī)劃的Top-k概率計算方法，將計算得出的Top-k概率和數(shù)據(jù)的屬性分值結(jié)合，得到一個新的排序參數(shù)，將得到的排序參數(shù)作為Top-k結(jié)果集的查詢標(biāo)準(zhǔn)，從而實(shí)現(xiàn)數(shù)據(jù)的概率與屬性分值的綜合考慮.文中對數(shù)據(jù)的兩個屬性都進(jìn)行約束，更加符合實(shí)際應(yīng)用中的操作需求.由于不確定Top-k查詢的計算量較為龐大，文中提出基于ETK查詢算法的剪枝規(guī)則，從而減少查詢工作量，提高算法的查詢效率.

1 相關(guān)知識

在不確定數(shù)據(jù)的研究領(lǐng)域中，數(shù)據(jù)的建模顯得尤為重要，可能世界是一種被廣泛應(yīng)用的研究模型[9].不確定數(shù)據(jù)庫D為概率數(shù)據(jù)庫，不確定數(shù)據(jù)庫中部分元組的一個集合構(gòu)成一個可能世界實(shí)例w，每個可能世界實(shí)例存在概率在[0,1]中，是在給定范圍內(nèi)的一個概率分布，不確定數(shù)據(jù)庫D中的所有可能世界實(shí)例構(gòu)成完整的可能世界空間Ω.

設(shè)D是一個不確定數(shù)據(jù)集，并且D由n個元組ti組成，ti∈D(i=1,2,…,n).每一個元組ti的形式為ti=(vi，pi)，其中vi為數(shù)據(jù)項(xiàng)ti的得分值，pi為ti在數(shù)據(jù)庫中出現(xiàn)的概率.

對于存在級不確定數(shù)據(jù)，其對象的所有屬性值均是確定的，而對象本身以一定的概率存在于數(shù)據(jù)庫中.顯然對于共有n個元組的不確定數(shù)據(jù)庫D，共有2n個可能世界.對于某一可能世界w∈Ω，根據(jù)可能世界語義模型，將其存在概率定義為

表1給出了元組ti的屬性值和相應(yīng)發(fā)生的概率，其中元組的屬性值是確定的.表2給出了可能世界實(shí)例及概率計算.

表1 元組屬性值和概率值

表2 可能世界實(shí)例及概率計算

如表2所示，共有23=8個可能世界實(shí)例w，不失一般性，其中w為空的情況一般不考慮.

數(shù)據(jù)的不確定性(概率問題)使得準(zhǔn)確描述實(shí)際應(yīng)用中的情況十分困難且不太現(xiàn)實(shí)，一般而言只能描述與可用信息一致的一組可能世界的集合.相比數(shù)據(jù)原有的概率屬性，可能世界模型的存在使得解決不確定數(shù)據(jù)的相關(guān)問題時，從不確定的數(shù)據(jù)庫轉(zhuǎn)化為確定的可能世界實(shí)例.

2 不確定Top-k查詢算法(ETK)

在Top-k查詢中，用戶往往只關(guān)注排名靠前的一部分?jǐn)?shù)據(jù)，對排名靠后的數(shù)據(jù)并不關(guān)心，因此并不需要對所有的數(shù)據(jù)都進(jìn)行排序計算.本節(jié)給出Top-k概率的計算方法以及一些剪枝規(guī)則用來對數(shù)據(jù)集進(jìn)行刪減，從而不必計算所有數(shù)據(jù)的Top-k概率以及排序參數(shù)，同時給定參數(shù)化不確定Top-k查詢算法.

定義1在一個給定的不確定數(shù)據(jù)集D中，對于任意的兩個元組ti，tj，如果元組ti的排序?qū)傩苑种敌∮诘扔谠Mtj的排序?qū)傩苑种?，那么稱為ti支配tj，用來ti

不確定數(shù)據(jù)集相對確定數(shù)據(jù)集，還存在一個概率的問題，因此僅僅是返回排序分值優(yōu)先的數(shù)據(jù)對象，并不能滿足不確定數(shù)據(jù)的查詢要求，所以還需要對數(shù)據(jù)的概率進(jìn)行排序.

定義2在一個給定的不確定數(shù)據(jù)集D={t1,t2,…，ti,…，tn}中，對于任意的兩個元組ti，tj，如果ti

定理1在一個給定的不確定數(shù)據(jù)集D={t1,t2,…，ti,…，tn}中，對于給定的數(shù)據(jù)元組ti，tj，tk，如果ti

證明因?yàn)閠i

2.1 Top-k概率及其計算

給定一個不確定數(shù)據(jù)集D，該數(shù)據(jù)集中的任一元組ti=(vi，pi)，其中vi為該元組的排序?qū)傩灾担琾i為該元組的存在概率，數(shù)據(jù)集D已經(jīng)按照屬性值vi降序排序(文中認(rèn)為排序?qū)傩灾翟酱笤胶?.不確定數(shù)據(jù)集的所有可能世界集合Ω={w1,w2,…，wn}，同時，使用Pr(wi)來表示可能世界實(shí)例wi的概率.在可能世界模型下的元組t的Top-k概率為所有可能世界實(shí)例中，可能世界空間Ω中所有包含元組t的可能世界實(shí)例的概率之和，表達(dá)式為

(1)

例如，表2中t2的Top-k概率為Pt(t)=Pr(w3)+Pr(w5)+Pr(w7)+Pr(w8)=0.224+0.056+0.096+0.024=0.400.

數(shù)據(jù)的Top-k概率經(jīng)由可能世界實(shí)例的累加運(yùn)算而得，相對于數(shù)據(jù)的存在概率，它是由確定的世界實(shí)例得來，因而在處理不確定數(shù)據(jù)時，更具有可靠性.

然而在實(shí)際運(yùn)算中，根據(jù)可能世界模型對可能世界空間Ω中包含元組t的所有可能世界實(shí)例進(jìn)行累加運(yùn)算會非常麻煩，因此，在這里引用了一個用于求解不確定數(shù)據(jù)的近似Top-k概率動態(tài)規(guī)劃算法.在ZHANG X.等[10]的文獻(xiàn)中，對此遞歸算法有具體的研究與說明，因算法較為復(fù)雜，在此不再贅述.

給定一個不確定數(shù)據(jù)集D，其中數(shù)據(jù)t已經(jīng)根據(jù)屬性分值的升序進(jìn)行排序，那么數(shù)據(jù)t的Top-k概率可以用以下公式來計算：當(dāng)1≤i≤k時，Pt(ti)=P(ti)；當(dāng)i>k時，

(2)

在k值為0時，默認(rèn)數(shù)據(jù)Top-k概率為0.根據(jù)值的大小對i進(jìn)行分類處理，在當(dāng)前數(shù)據(jù)下標(biāo)i比k小的情況下，數(shù)據(jù)t的Top-k概率即為數(shù)據(jù)的本身存在概率，當(dāng)數(shù)據(jù)下標(biāo)i大于k時，即可用遞歸公式進(jìn)行數(shù)據(jù)的Top-k概率計算.

2.2 剪枝方法

由于不確定數(shù)據(jù)的數(shù)據(jù)量十分龐大，隨著數(shù)據(jù)量的增加，查詢工作的計算量是呈指數(shù)增長的，所以在進(jìn)行Top-k查詢處理的時候，計算量過大，因此提出一些剪枝規(guī)則來減少計算量.

定義3對于一個給定的不確定數(shù)據(jù)集D，一個屬性分值的約束范圍R=[fmin,fmax]，文中的Top-k查詢要求返回結(jié)果集中的數(shù)據(jù)要滿足數(shù)據(jù)的屬性分值都在R的約束范圍內(nèi).

剪枝方法1給定一個不確定數(shù)據(jù)集D，一個分值函數(shù)F，和一個屬性分值約束范圍[fmin,fmax].對于在數(shù)據(jù)集D中的任意不確定數(shù)據(jù)t，如果t的屬性分值不在分值約束范圍R內(nèi)，那么數(shù)據(jù)t可以從D中直接剪枝.

定義4用戶根據(jù)需求來給定一個概率閾值α，要求最后的Top-k結(jié)果集中的元組滿足：{t|t∈D,Pt(t)>α}，其中Pt(t)即為2.1中所求得的數(shù)據(jù)元組的Top-k概率.

定理2給定一個不確定數(shù)據(jù)集D，對于任意的不確定元組t∈D，如果元組t的Top-k概率Pt(t)≤P(t)，那么不確定數(shù)據(jù)集D中的任意一個元組t的Top-k概率都不會超過該元組的存在概率.

證明基于可能世界實(shí)例的語義模型，對于任意的不確定數(shù)據(jù)t∈D，t的Top-k概率是包含了t的所有可能世界實(shí)例的概率總和[11]，即為

對于任意的可能世界實(shí)例w∈Ω，如果t∈w并且w中最多只有k-1個元組比t有更高的得分值，那么t的Top-k概率符合所求，在此假設(shè)所有的不確定數(shù)據(jù)之間都是互相獨(dú)立，沒有相互影響規(guī)則的，所以有

由可能世界語義模型可知，對于所有的w∈Ω,都有

所以，有

故可得

Pt(t) ≤P(t).

證畢.

剪枝方法2給定一個不確定數(shù)據(jù)集D，一個用戶根據(jù)需求定義的概率閾值α.對于數(shù)據(jù)集D中的任意不確定數(shù)據(jù)元組t，如果元組t的存在概率P(t)∈α，那么數(shù)據(jù)t可以從D中直接剪枝.

證明因?yàn)镻(t)∈α，由定理2可得Pt(t)≤P(t)≤α，根據(jù)概率閾值的Top-k查詢可知，結(jié)果集中的元組t的Top-k概率必須大于α，所以元組t不屬于最終的結(jié)果集.

2.3 ETK查詢算法

定義5在一個給定的不確定數(shù)據(jù)集D={t1,t2,…，ti,…，tn}中，對于任意的兩個元組ti，tj，假設(shè)S(ti)，S(tj)分別為元組ti，tj的Top-k概率與屬性分值的乘積，如果S(ti)≥S(tj)，那么稱為ti排序支配tj，用ti

在不確定數(shù)據(jù)集D中，數(shù)據(jù)已經(jīng)按照屬性分值大小進(jìn)行排序，然后將Top-k概率引入到查詢語義中，將參數(shù)化排序函數(shù)值S(t)定義為元組t的Top-k概率與屬性值的乘積，計算式為

文中將計算得出的S(t)定義為排序的參數(shù)，在Top-k查詢中用S(t)作為排序的標(biāo)準(zhǔn)，在數(shù)據(jù)的屬性分值和Top-k概率都滿足約束條件的情況下，選取S(t)排序在前k的數(shù)據(jù).

在不確定數(shù)據(jù)集D中，對于剪枝過后的數(shù)據(jù)集，計算得出每個數(shù)據(jù)的排序參數(shù)S(t)，并且根據(jù)S(t)對數(shù)據(jù)進(jìn)行排序，選取排在前k位的數(shù)據(jù)，并且要求數(shù)據(jù)的屬性分值在給定的分值范圍R內(nèi)，且Top-k概率不小于概率閾值α.

首先初始化結(jié)果集為空用來存儲最后的Top-k查詢結(jié)果；然后對于不確定數(shù)據(jù)集D進(jìn)行分值和概率閾值的約束；再按照分值的降序排序，計算得出剩余數(shù)據(jù)集中數(shù)據(jù)的Top-k概率；最后對數(shù)據(jù)集進(jìn)行最后的刪減，計算得出剩余數(shù)據(jù)集的排序參數(shù)，將排序在前k的數(shù)據(jù)送入S中并且返回結(jié)果集.

ETK查詢的輸入如下：一個不確定數(shù)據(jù)集D,概率閾值α,一個正整數(shù)k,屬性分值F，約束范圍R=[fmin,fmax].其輸出包含了所有ETK查詢結(jié)果的集合S.ETK查詢算法的偽代碼如下：

initialize the Top-kanswer setS=?;

for each tupletinDdo

if (P(t)<αorF(t)?R) then

Remove(t);(移除數(shù)據(jù)t，剪枝方法1和2)

Sort(t);(對剩余數(shù)據(jù)進(jìn)行排序)

for the remaining tuples inDdo

Compute(t);(計算數(shù)據(jù)Top-k概率，見式2)

Remove tupletfrom the databaseD;

compute theS(t)=F(t)·Pt(t) of each tuple remaining;

selectktuples which have the maximumS(t) score and Top-kprobability no less than α,and put them into the answer setS;

returnS.

3 試驗(yàn)與結(jié)果分析

針對以上提出的ETK算法進(jìn)行了一部分試驗(yàn)來驗(yàn)證算法的執(zhí)行效率以及準(zhǔn)確性.試驗(yàn)在一個單機(jī)環(huán)境下進(jìn)行，CPU為Intel(R)Core(TM)i7-6700HQ ，4核，主頻2.6 GHz，內(nèi)存8 GB，操作系統(tǒng)為64位win10.算法采用Visual Studio 2013實(shí)現(xiàn).

采用國際冰情監(jiān)視工作站(international ice patrol,IIP)所收集的關(guān)于冰山漂移情況的數(shù)據(jù)庫來驗(yàn)證算法的有效性.數(shù)據(jù)集中的每個記錄當(dāng)作一個元組，每個觀測記錄都由于觀測點(diǎn)的不同而具有不同的可信度，把幾個觀測點(diǎn)的可信度分別用概率值0.3,0.4,0.5,0.6,0.7表示，這些概率即為元組的存在概率.

試驗(yàn)中的數(shù)據(jù)集T1，T2分別為從2007，2009年冰山漂移數(shù)據(jù)中選取的數(shù)據(jù)，各包含6 000，13 000條數(shù)據(jù).圖1是在數(shù)據(jù)集T1上進(jìn)行的比較，圖2是在數(shù)據(jù)量n為3 000，6 000，9 000，12 000，15 000情況下的比較.

圖1 在數(shù)據(jù)集T1上的比較

圖2 數(shù)據(jù)集不同情況下的查詢時間

在圖1和圖2中，取概率閾值α=0.5，這兩組試驗(yàn)對文中提出的ETK查詢算法與傳統(tǒng)U-Topk查詢算法以及參數(shù)化排序中的E-score查詢算法進(jìn)行時間上的比較，在經(jīng)過文中提出的基于Top-k概率的剪枝方法后，ETK算法的查詢時間明顯少于U-Topk和E-score算法，在k值增大的時候，減少的查詢時間較為明顯，而在數(shù)據(jù)量較大的時候，ETK的性能提升則較為明顯，查詢時間也明顯減少.

圖3給出了ETK查詢算法在k值不同情況下查詢時間的變化.

圖3 不同k下的查詢時間

由圖3可見，在k逐漸增大的過程中，結(jié)果集中的數(shù)據(jù)量逐漸變多，所以Top-k概率以及S(t)的計算量增加了許多，即導(dǎo)致了算法的查詢運(yùn)行時間隨著k值的增加而變大，可以看到數(shù)據(jù)集的增加會使得運(yùn)行時間變化較為明顯.

圖4給出了文中ETK查詢算法在概率閾值α取不同值下進(jìn)行查詢的時間變化.

圖4 不同α下的查詢時間

由圖4可見，概率閾值α的選取對算法的運(yùn)行時間有著很大的影響，文中不探討概率閾值的選取問題.根據(jù)閾值與數(shù)據(jù)的關(guān)系可知，α取值越大，被剪枝掉的數(shù)據(jù)就越多，因此需要進(jìn)行的計算就越少，所以隨著α逐漸增加，運(yùn)行所需要時間也越來越少.

4 結(jié) 論

1) ETK算法引用可能世界模型計算得出的Top-k概率，從數(shù)據(jù)原有的概率轉(zhuǎn)化為數(shù)據(jù)的Top-k概率，實(shí)現(xiàn)了從不確定概率到確定可能世界實(shí)例的轉(zhuǎn)變，在算法的可行性上有所提高.

2) 算法中提出了基于Top-k概率以及概率閾值的相關(guān)剪枝技術(shù)，在對數(shù)據(jù)進(jìn)行查詢處理之前，實(shí)現(xiàn)了對數(shù)據(jù)集的縮減，大大的減少了計算量.

3) 試驗(yàn)部分通過與以往算法的對比，以及對不同參數(shù)情況下的對比，進(jìn)一步證明算法在時間性能上的提升，驗(yàn)證了算法的有效性.