不確定數(shù)據(jù)Top—K查詢技術(shù)研究

黃玲玲　楊剴

摘要：高效的Top-K查詢處理是不確定數(shù)據(jù)管理的一項重要技術(shù)。從確定性算法技術(shù)和近似算法技術(shù)兩方面研究典型的不確定數(shù)據(jù)的Top-K查詢算法，分析概率與分值的平衡方式，介紹統(tǒng)一化排序思想以及綜合多種查詢特征的新型查詢方式，最后提出不確定性Top-K查詢的研究方向及不確定性查詢處理技術(shù)的研究熱點。

關(guān)鍵字：不確定性數(shù)據(jù)；Top-K查詢；確定算法技術(shù)；近似算法技術(shù)；排序函數(shù)；概率

中圖分類號 TP311 文獻標志碼：A

0 引言

隨著傳感器網(wǎng)絡和移動對象的應用，不確定數(shù)據(jù)無處不在，如傳感器數(shù)據(jù)、RFID數(shù)據(jù)、隱私數(shù)據(jù)、LBS數(shù)據(jù)、Web應用數(shù)據(jù)等等。同時人們也逐漸認識到不確定數(shù)據(jù)處理帶來的巨大價值。目前，不確定數(shù)據(jù)查詢技術(shù)已經(jīng)成為空間和移動數(shù)據(jù)庫的前沿研究領(lǐng)域[1]。其中面向不確定數(shù)據(jù)庫的Top-K查詢處理在涉及大量數(shù)據(jù)交互方面的拓展應用則是一項高效基礎(chǔ)重要技術(shù)[2]。面向確定數(shù)據(jù)庫的Top-K查詢的定義非常清晰，即返回Ranking函數(shù)值最大的K個元組。但是，由于不確定數(shù)據(jù)概率維度的存在，確定數(shù)據(jù)集上的Top-K查詢算法無法直接應用到不確定數(shù)據(jù)集合上[3]?；诖?，本文擬從確定性算法技術(shù)和近似算法技術(shù)兩方面展開典型不確定數(shù)據(jù)的Top-K查詢算法研究，同時分類綜述近年來不確定數(shù)據(jù)Top-K查詢的研究成果，并指出下一步的的挑戰(zhàn)與發(fā)展方向。

1 典型不確定數(shù)據(jù)Top-K定義和算法研究

針對不確定性Top-K查詢，學者們從多種應用需要以及設(shè)定側(cè)面給出了不同的查詢語義。其中U-TopK[4，5]、U-kRanks[4，6]、c-typical-Topk[7]、Global-TopK[8]、PT-K[9-11]、Expected Rank[12-13]等得到了廣泛認同，而且可分別適用于不同的應用場景。與此同時，不確定查詢算法隨即進入了深度探索的研究完善階段。對不確定查詢處理的確定性算法技術(shù)的研究焦點就是如何利用查詢語義的特點避免展開整個可能世界空間[4-5，7-10，12-13]，從而提高查詢效率。

1.1 確定性算法技術(shù)

Re等人[14]較早地研究了概率數(shù)據(jù)庫中的Top-K查詢問題，闡述了通過SQL語句查詢概率數(shù)據(jù)中概率值最大的Top-K元組，其元組的概率即為排序函數(shù)值。然而，多數(shù)不確定數(shù)據(jù)上的Top-K查詢通常在可能的世界模型語義下聚集查詢結(jié)果來排序概率數(shù)據(jù)以獲取查詢結(jié)果。

Soliman等人[4]針對不確定數(shù)據(jù)上的Top-K查詢問題，首次研究提出了解決查詢的不確定數(shù)據(jù)模型以及U-TopK查詢和U-KRanks查詢的定義。

概括來說，U-TopK查詢返回一個長度為K的元組矢量，而且是在所有的可能世界中的發(fā)生概率為最大；U-KRanks查詢返回在各個級別中出現(xiàn)的總概率最大的元組。Soliman證明了按分值排序讀取記錄可以使U-TopK查詢和U-KRanks查詢讀取最少記錄完成查詢，并設(shè)計實現(xiàn)了可確保最優(yōu)性的查詢算法。因此，這2種查詢方法就是將查詢問題轉(zhuǎn)化為狀態(tài)空間搜索問題，研究轉(zhuǎn)化為實例化最少的狀態(tài)。各元組首先按照ranking函數(shù)從小到大進行排序，然后不斷構(gòu)造搜索空間，縮小空間的范圍，最終獲得查詢結(jié)果。

在c-typical-TopK查詢中也使用了狀態(tài)空間擴展方法。當所求的Top-K具有最優(yōu)子結(jié)構(gòu)性質(zhì)時，還可以采用動態(tài)規(guī)劃的方法。動態(tài)規(guī)劃的目標是發(fā)現(xiàn)求解Top-K問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。文獻[7]中求解的c-typical-TopK和文獻[5]中求解的Global TopK都表現(xiàn)出同樣性質(zhì)。

動態(tài)規(guī)劃算法滿足最優(yōu)化原理，能夠?qū)⑶蠼獾膯栴}分解成若干個子問題（階段），且下一個子階段的求解依賴于上一個子階段的運行結(jié)果，最終就是一句尾端子階段的求解來依次求得其它階段的輸出解。

在確定性算法中，除了前文提到的狀態(tài)空間方法和動態(tài)規(guī)劃方法外，泊松二項遞推的方法也是常用方法之一。

當不確定性數(shù)據(jù)庫只存在記錄級不確定性且并未提供生存規(guī)則時，可以將每條記錄的出現(xiàn)與否視作實驗的2種對立結(jié)果：n次實驗代表數(shù)據(jù)庫的n條記錄。如PT-K查詢和global-TopK查詢都需要求解每條記錄出現(xiàn)在Top-K中的概率。如果將記錄按分值排序，記錄t出現(xiàn)在Top-K中的概率可以理解為如下表述事件：在排隊序列中，排位在t前的那些記錄同時出現(xiàn)小于等于k-1個記錄的概率，因此可以使用泊松二項分布的遞推方法[2]。

記錄級不確定數(shù)據(jù)庫大致滿足泊松二項分布的條件，在多種Top-K處理中都體現(xiàn)了泊松二項遞推的思想[9-11，15-17]。當探知生存規(guī)則時，只要對生存規(guī)則設(shè)計具體處理，就可以將問題轉(zhuǎn)化成簡單情況。

由于不確定性Top-K查詢處理建立在不確定數(shù)據(jù)模型和可能世界語義的基礎(chǔ)上，而可能世界空間隨著數(shù)據(jù)量成指數(shù)增長，由此則導致許多求解問題均具有NP難度。因此，近似算法應運而生，并能以較高的精確度大幅提升求解速度。

1.2 近似算法技術(shù)

文獻[10]不僅提出了概率閾值PT-K查詢定義，并針對此研究開發(fā)提出了高效的精確查詢算法和快速的抽樣近似查詢算法。

在求取PT-K時，在可能世界空間改善可能世界實例。每取樣一個可能世界實例，即對出現(xiàn)在Top-K中的記錄ID控制加1。在樣本足夠多的情況下，記錄的累計頻度接近該記錄的真實Top-K概率。

因此，在用戶不需要完全精確答案的前提下，為了進一步提高查詢效率，很多學者都采用近似的方法來處理不確定性Top-K查詢，以犧牲少量精度的方式換取更高的處理效率[5，9-10，13，15-16，18]。

在不確定性Top-K的確定算法處理技術(shù)中，關(guān)鍵求解概率大多具有遞減性質(zhì)，并依賴一些其它的限制條件，在求解一些特定不確定性Top-K時，本來需要掃描所有記錄，但是根據(jù)一些已知條件會發(fā)現(xiàn)某位置后的記錄在解集中的可能性微乎其微，因此可以利用已知結(jié)果維護一個逐漸逼近真實值的閾值，使得求解為精確度非常高的近似解集。expected Rank Top-K[12-13]和global Top-K[8，19]就采用了逼近閾值的近似求解來支持設(shè)計實現(xiàn)的。

例如，在expected Rank 求解中，需要求解每個記錄在所有可能世界的期望位置，再求取其中最好的k個?？砂捶种灯谕樞驋呙栌涗?，不斷更新已掃描記錄的期望排位上限，并重新計算尾部記錄排位下限。當有k個記錄的排位上限大于尾部記錄排位下限時算法結(jié)束，得到的結(jié)果將具有接近理想的近似程度。

Global-TopK則是使用記錄分值排序表1和記錄概率排序表2兩個列表，掃描表1，并計算當前掃描記錄的概率，利用表2和當前掃描記錄來估算所有未見記錄的global Top-K上限，設(shè)定閾值進行剪枝加速算法。

可見，閾值逼近通過掃描按特定順序排列的記錄，不斷更新某些特定值以逼近停止條件。雖然在算法結(jié)構(gòu)上沒有明顯改進，但是因為在保證一定精確度的前提下限制了掃描記錄的數(shù)量，極大的縮短了求解時間，有時甚至可達數(shù)量級的變動，從而優(yōu)勢提升了查詢效率。

除了閾值逼近以外，近似求解也可通過近似取樣技術(shù)和近似計算技術(shù)而獲取生成。近似取樣技術(shù)采用隨機采樣技術(shù)（即蒙特卡羅—MonteCarlo方法[20]），保證了在具有巨大實例數(shù)目的可能世界中隨機選取部分實際樣本且樣本達到一定數(shù)目的條件下，計算的概率能夠比較接近于真實結(jié)果。近似計算技術(shù)則需要合理構(gòu)建不確定數(shù)據(jù)的概率分布函數(shù)來計算概率的近似值，以此來最佳提升計算的效率，如泊松分布近似計算方法。

獨立樣本使用基本的蒙特卡羅方法產(chǎn)生，分值連續(xù)時，求解各種不確定性Top-K查詢時需要在聯(lián)合概率密度函數(shù)上進行積分運算，使用馬爾可夫鏈的蒙特卡羅方法[21]，保證以高概率的方式取樣到有效的可能世界，提高近似程度。如MS-TopK查詢的蒙特卡羅取樣方法[22]、PT-K查詢的蒙特卡羅積分方法[23]、U-TopK查詢的動態(tài)馬爾可夫取樣方法[24]。

綜上所述可知，確定性算法一般要比近似算法復雜程度高，而近似算法通過少量精度損失卻可大幅提升查詢效率。

2分值與概率的平衡研究

Li采用規(guī)范Kendall距離[15]對比同一數(shù)據(jù)集上的5種不確定性Top-K返回的結(jié)果，發(fā)現(xiàn)各語義返回結(jié)果差異顯著，有些結(jié)果甚至完全相反。究其原因，主要有2點，分別是：記錄的概率和Ranking函數(shù)分值。

通常有3種方式來處理分值和概率這兩大因素：

1）先進行分值排序再求取概率，如U-TopK。但是在利用分值求得所有的Top-K序列后，再將概率作為唯一的衡量標準，將導致弊端紛顯，因而應將分值重新納入考量范疇。

2）先求取概率，再進行分值排序，如文獻[5]中指出在位置概率U-iRanks的基礎(chǔ)上根據(jù)Top-K位置上記錄的位置概率總和最大來進行優(yōu)化，利用二分圖匹配的方式找出最優(yōu)排序。但是這種平衡方式可能使得到的結(jié)果序列在任何可能世界均不存在，并且也不是所有場景都能使用概率總和最大化目標的求解方式。

3）同時綜合考慮概率和排序，如global TopK和Expected Rank。

分值與排序的平衡方式一直是不確定數(shù)據(jù)Top-K查詢的重要研究問題。事實上，在平衡概率和分值時，各種不確定性Top-K語義根據(jù)不同的應用需要，分別設(shè)定了各自的權(quán)衡標準，滿足各自應用部分的排序要求。Li等人[15]在分析各種排序函數(shù)定義缺點的基礎(chǔ)上，嘗試研究統(tǒng)一化排序，把概率數(shù)據(jù)庫上的Top-K查詢問題看成多目標化問題，并且提出一種通用的處理框架和帶有2種參數(shù)的排序函數(shù)PRFw和PRFc。參數(shù)的選取直接關(guān)系分值與概率的平衡，而且不同的參數(shù)的設(shè)置使用戶能夠靈活改變查詢結(jié)果。

然而由于缺少顯式的選擇函數(shù)和參數(shù)描述，需要用戶定義合適的排序函數(shù)及參數(shù)是很困難的。裴建等人[25]提出概率Skyline查詢的概念以檢索Skyline概率大于某個閾值的不確定對象，避免了用戶定義排序函數(shù)。但是可能導致無法控制返回結(jié)果的數(shù)目，因此，用戶還是需要設(shè)置具體概率閾值。

為了解決概率閾值難于設(shè)置的問題，研究嘗試將Top-K查詢與其它查詢方式聯(lián)合起來，配置支持拓展開發(fā)。文獻[26]將Top-K查詢與Skyline相結(jié)合，提出概率Top-K支配（PTD）查詢的定義，使其具有Skyline查詢和概率排序查詢的優(yōu)點，能夠獲得針對某個查詢點具有最大支配能力的k個不確定對象。文獻[27]將傳統(tǒng)的聚集查詢與Top-K查詢相結(jié)合，提出排序-聚集查詢的概念，通過建?？臻g搜索問題、引入具有保證性的空間搜索算法和流水線的處理框架，部分枚舉解空間快速獲得查詢結(jié)果。這種綜合多種查詢特征的新型查詢方式可以獲得多種查詢的優(yōu)勢，使得查詢結(jié)果更有利于實際應用。

3 結(jié)束語

綜合國內(nèi)外不確定性Top-K查詢的研究現(xiàn)狀以及最新研究成果，如何開發(fā)高效的查詢處理方法、如何平衡分值與概率、如何設(shè)計滿足不同應用環(huán)境的新型查詢語義依然是未來研究的重要方向。此外，由于很多現(xiàn)實應用領(lǐng)域數(shù)據(jù)環(huán)境的不確定性和復雜性，例如分布式系統(tǒng)、高維數(shù)據(jù)庫、數(shù)據(jù)流等，使得在這種環(huán)境下的不確定性Top-K查詢正日趨現(xiàn)實具體與復雜。分布式系統(tǒng)中如何降低交互程度[28-30]、不確定數(shù)據(jù)流上Top-K查詢時間維的處理[31-32]、高維數(shù)據(jù)庫因維度提高而帶來的Top-K語義變化和查詢效率問題將成為研究焦點。因此，分布式環(huán)境下不確定數(shù)據(jù)查詢方法[33-34]、基于流數(shù)據(jù)環(huán)境下不確定數(shù)據(jù)查詢方法[35-37]、基于高維數(shù)據(jù)庫的不確定查詢算法[30，38-41]亦可能成為未來持續(xù)研究熱點。

參考文獻：

[1] 蔣濤，高云君，張彬，等. 不確定數(shù)據(jù)查詢處理[J]. 電子學報，2013，41（5）：966-976.

[2] 李文鳳， 彭智勇， 李德毅. 不確定性Top-K 查詢處理[J]. 軟件學報，2012，23（6）：1542-1560.

[3]郭長友，鄭雪峰，高秀蓮. 基于不確定理論的不確定性數(shù)據(jù)Top-k查詢計算[J]. 計算機科學.2016，43（3）：225-230.

[4] SOLIMAN M A， LLYAS I F， CHANG K C C. Top-K query processing in uncertain databases[C]//

IEEE International Conference on Data Engineering. Washington： IEEE Computer Society Press， 2007. 896-905.

[5] SOLIMAN M A， LLYAS I F. Ranking with uncertain scores[C]//IEEE International Conference on Data Engineering. Washington：IEEE Computer Society Press， 2009：317-328.

[6] LIAN L， CHEN L. Probabilistic ranked queries in uncertain databases[C]//International Conference on EDBT.New York： ACM Press，2008： 511-522.

[7] GE Tingjian， ZDONIK S， MADDEN S. Top-K queries on uncertain data： on score distribution and typical answers[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. Rhode Island， USA：ACM，2009： 375-388.

[8] ZHANG X， CHOMICKI J. On the semantics and evaluation of Top-K queries in probabilistic databases[J]. Distributed and Parallel Databases， 2009， 26（1）：67-126.

[9] Hua M， Pei J， Zhang WJ， Lin XM. Ranking queries on uncertain data： A probabilistic threshold approach[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver， Canada：ACM， 2008. 673-686.

[10] Hua M， Pei J， Zhang W J， et al. Efficiently answering probabilistic threshold Top-k queries on uncertain data[R]//Burnaby：Simon Fraser University，2007.

[11] HUA M， PEI J. Ranking queries on uncertain data[J]. The VLDB Journal， 2011， 42（1）：9-32.

[12] CORMODE G， LI F， YI K. Semantics of ranking queries for probabilistic data and expected ranks[C]//IEEE International Conference on Data Engineering. Washington： IEEE Computer Society Press， 2009， 23（12）：305-316.

[13] JESTES J， CORMODE G， LI F， et al. Semantics of ranking queries for probabilistic data[J]. IEEE Transactions on Knowledge & Data Engineering， 2010，23（12）：305-316.

[14] RE C，DALVI N， DAN S. Efficient top-k query evaluation on probabilistic data[C] //Proc of Int Conf on Data Engineering（ICDE）. Piscataway，NJ：IEEE，2007：886-895.

[15] LI J， SAHA B， DESHPANDE A. A unified approach to ranking in probabilistic databases[J]. The VLDB Journal， 2011，20（2）：249-275.

[16] LI J， DESHPANDE A. Ranking continuous probabilistic datasets[J]. Proceedings of the Vldb Endowment， 2010，3（1-2）：638-649.

[17] YI K， LI F， KOLLIOS G， et al. Efficient processing of Top-k queries in uncertain databases[C]//IEEE International Conference on Data Engineering. Cancun， Mexico：IEEE，2008，20（12）：1406-1408.

[18] GE T， ZDONIK S. Handling uncertain data in array database systems[C]//IEEE International Conference on Data Engineering.Cancun， Mexico： IEEE， 2008：1140-1149.

[19] ZHANG X， CHOMICKI J. On the semantics and evaluation of Top-K queries in probabilistic databases[J]. Journal of Distributed and Parallel Databases， 2009，26（1）：67-126.

[20] KARP R M，LUBY M.Monte-carlo algorithms for enumeration and reliability problems[C]//24th Annual Symposium on Foundations of Computer Science （sfcs 1983）. Tucson， Arizona，1983：56-64.

[21] SOLIMAN M A， LLYAS I F，BEN-DAVID S.Supporting rankingqueries on uncertain and incomplete data[J].The VLDB Journal，2010，19（4）：477-501.

[22] RE C，DALVI N， SUCIU D. Efficient top-k query evaluation onprobabilistic data[C]//Proc of IEEE ICDE Conf. Istanbul，Turkey：IEEE Computer Society，2007：886-895.

[23] HUA Ming， PEI Jian， LIN Xue-ming. Ranking queries on uncertain data[J].The VLDB Journal，2011，20（1）：129-153.

[24] SOLIMAN M A， LLYAS I F，CHANG C C.Probabilistic top-k and ranking-aggregate queries[J].Acm Transactions on Database Systems，2008，33（3）：15-19.

[25] PEI J，JIANG B，LIN X，et al.Probabilistic skylines on uncertain data[C] //International Conference on Very Large Data Bases.Kohala coast， Hawaii：ACM，2015，38（1）：1-39.

[26] LIAN X，CHEN L.Top-k dominating queries in uncertain databases[C] // Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology.Saint Petersburg， Russia：ACM，2009：660-671.

[27] SOLIMAN M A，LLYAS I F， CHANG C C.Probabilistic top-k and ranking-aggregate queries[J].ACM Trans on Database Systems（TODS）.2008，33（3）：15-19.

[28] WANG G， YUAN Y， SUN Y， et al. PeerLearning： A content-based e-learning material sharing system based on P2P network[J]. World Wide Web， 2011，13（3）：275-305.

[29] LI F， YI K， JESTES J. Ranking distributed probabilistic data[C]//Acm Sigmod International Conference on Management of Data. Providence， RI， USA： ACM ， 2009：361-374.

[30] EL-DESOUKY A/， ALI H/， ABDUL-AZEEM Y M. Ranking distributed uncertain database systems： Discussion and analysis[C]//International Conference on Computer Engineering & Systems. Cairo， Egypt：IEEE，2010，54（1）：295-300.

[31] JIN C Q， YI K， CHEN L， et al. Sliding window Top-K queries on uncertain streams[J]. The VLDB Journal， 2010，19（3）：411-435.

[32] JIN C Q， GAO M， ZHOU A Y. Handling ER-Top K query on uncertain streams[M]// HUTCHISON D， KANADE T， KITTLER J， et al. Lecture Notes in Computer Science， Berlin Heidelberg：Springer ，2011，6587：326-340.

[33] LI Feifei，YI Ke， JESTES J. Ranking distributed probabilistic data[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of data.Rhode Island，USA：ACM，2009：361-374.

[34] DING Xiaofeng，JIN Hai. Efficient and progressive algorithms for distributed skyline queries over uncertain data[J].IEEE Trans on Knowl and Data Eng，2012，24（8）：1448-1462

[35] JIN Cheqing，YI Ke，CHEN Lei，et al. Sliding-window top-k queries on uncertain streams[J].The VLDB Journal，2010，19（3）：411-435.

[36] LIAN Xiang，CHEN Lei.Similarity join processing on uncertain data streams[J].IEEE Trans on Konwl and Data Eng，2011，23（11）：1718-1734.

[37] DING Xiaofeng， LIAN Xiang， CHEN Lei， et al. Continuous monitoring of skylines over uncertain data streams[J].Information Sciences，2012，184（1）：196-214.

[38] BESKALES G， SOLIMAN M A， IIYAS I F. Efficient search for the Top-k probable nearest neighbors in uncertain databases[J]. Journal Proc.of VLDB Endowment， 2008，1（1）：326-339.

[39] ZHANG Ying， ZHANG Wenjie， LIN Xuemin， Jiang B， Pei J. Ranking uncertain sky： The probabilistic Top-K skyline operator. In： Proc. of the Information Systems. 2011. 898915.

[40] LIAN X， CHEN L. Shooting Top-k stars in uncertain databases[J]. Journal of VLDB， 2011，20（6）：819-840.

[41] Wang C H. Top-K ranking with uncertain data [D]. Edmonton： University of Alberta， 2012.