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

1、 不確定數(shù)據(jù)TopK查詢技術(shù)研究 黃玲玲楊剴Summary：高效的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 文獻(xiàn)標(biāo)志碼：A0 引言隨著傳感器網(wǎng)絡(luò)和移動對象的應(yīng)用，不確定數(shù)據(jù)無處不在，如傳感器數(shù)據(jù)、RFID數(shù)據(jù)、隱私數(shù)據(jù)、LBS數(shù)據(jù)、Web應(yīng)用數(shù)據(jù)等等。同時人們也逐漸認(rèn)

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

3、義和算法研究針對不確定性Top-K查詢，學(xué)者們從多種應(yīng)用需要以及設(shè)定側(cè)面給出了不同的查詢語義。其中U-TopK4，5、U-kRanks4，6、c-typical-Topk7、Global-TopK8、PT-K9-11、Expected Rank12-13等得到了廣泛認(rèn)同，而且可分別適用于不同的應(yīng)用場景。與此同時，不確定查詢算法隨即進(jìn)入了深度探索的研究完善階段。對不確定查詢處理的確定性算法技術(shù)的研究焦點就是如何利用查詢語義的特點避免展開整個可能世界空間4-5，7-10，12-13，從而提高查詢效率。1.1 確定性算法技術(shù)Re等人14較早地研究了概率數(shù)據(jù)庫中的Top-K查詢問題，闡述了通過SQL語

4、句查詢概率數(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)了可確

5、保最優(yōu)性的查詢算法。因此，這2種查詢方法就是將查詢問題轉(zhuǎn)化為狀態(tài)空間搜索問題，研究轉(zhuǎn)化為實例化最少的狀態(tài)。各元組首先按照ranking函數(shù)從小到大進(jìn)行排序，然后不斷構(gòu)造搜索空間，縮小空間的范圍，最終獲得查詢結(jié)果。在c-typical-TopK查詢中也使用了狀態(tài)空間擴(kuò)展方法。當(dāng)所求的Top-K具有最優(yōu)子結(jié)構(gòu)性質(zhì)時，還可以采用動態(tài)規(guī)劃的方法。動態(tài)規(guī)劃的目標(biāo)是發(fā)現(xiàn)求解Top-K問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。文獻(xiàn)7中求解的c-typical-TopK和文獻(xiàn)5中求解的Global TopK都表現(xiàn)出同樣性質(zhì)。動態(tài)規(guī)劃算法滿足最優(yōu)化原理，能夠?qū)⑶蠼獾膯栴}分解成若干個子問題（階段），且下一個子階段的求解依賴于上一個子

6、階段的運行結(jié)果，最終就是一句尾端子階段的求解來依次求得其它階段的輸出解。在確定性算法中，除了前文提到的狀態(tài)空間方法和動態(tài)規(guī)劃方法外，泊松二項遞推的方法也是常用方法之一。當(dāng)不確定性數(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ù)庫大致滿足

7、泊松二項分布的條件，在多種Top-K處理中都體現(xiàn)了泊松二項遞推的思想9-11，15-17。當(dāng)探知生存規(guī)則時，只要對生存規(guī)則設(shè)計具體處理，就可以將問題轉(zhuǎn)化成簡單情況。由于不確定性Top-K查詢處理建立在不確定數(shù)據(jù)模型和可能世界語義的基礎(chǔ)上，而可能世界空間隨著數(shù)據(jù)量成指數(shù)增長，由此則導(dǎo)致許多求解問題均具有NP難度。因此，近似算法應(yīng)運而生，并能以較高的精確度大幅提升求解速度。1.2 近似算法技術(shù)文獻(xiàn)10不僅提出了概率閾值PT-K查詢定義，并針對此研究開發(fā)提出了高效的精確查詢算法和快速的抽樣近似查詢算法。在求取PT-K時，在可能世界空間改善可能世界實例。每取樣一個可能世界實例，即對出現(xiàn)在Top-K中的

8、記錄ID控制加1。在樣本足夠多的情況下，記錄的累計頻度接近該記錄的真實Top-K概率。因此，在用戶不需要完全精確答案的前提下，為了進(jìn)一步提高查詢效率，很多學(xué)者都采用近似的方法來處理不確定性Top-K查詢，以犧牲少量精度的方式換取更高的處理效率5，9-10，13，15-16，18。在不確定性Top-K的確定算法處理技術(shù)中，關(guān)鍵求解概率大多具有遞減性質(zhì)，并依賴一些其它的限制條件，在求解一些特定不確定性Top-K時，本來需要掃描所有記錄，但是根據(jù)一些已知條件會發(fā)現(xiàn)某位置后的記錄在解集中的可能性微乎其微，因此可以利用已知結(jié)果維護(hù)一個逐漸逼近真實值的閾值，使得求解為精確度非常高的近似解集。expecte

9、d Rank Top-K12-13和global Top-K8，19就采用了逼近閾值的近似求解來支持設(shè)計實現(xiàn)的。 例如，在expected Rank 求解中，需要求解每個記錄在所有可能世界的期望位置，再求取其中最好的k個?？砂捶种灯谕樞驋呙栌涗?，不斷更新已掃描記錄的期望排位上限，并重新計算尾部記錄排位下限。當(dāng)有k個記錄的排位上限大于尾部記錄排位下限時算法結(jié)束，得到的結(jié)果將具有接近理想的近似程度。Global-TopK則是使用記錄分值排序表1和記錄概率排序表2兩個列表，掃描表1，并計算當(dāng)前掃描記錄的概率，利用表2和當(dāng)前掃描記錄來估算所有未見記錄的global Top-K上限，設(shè)定閾值進(jìn)行剪枝加

10、速算法?？梢姡撝当平ㄟ^掃描按特定順序排列的記錄，不斷更新某些特定值以逼近停止條件。雖然在算法結(jié)構(gòu)上沒有明顯改進(jìn)，但是因為在保證一定精確度的前提下限制了掃描記錄的數(shù)量，極大的縮短了求解時間，有時甚至可達(dá)數(shù)量級的變動，從而優(yōu)勢提升了查詢效率。除了閾值逼近以外，近似求解也可通過近似取樣技術(shù)和近似計算技術(shù)而獲取生成。近似取樣技術(shù)采用隨機(jī)采樣技術(shù)（即蒙特卡羅MonteCarlo方法20），保證了在具有巨大實例數(shù)目的可能世界中隨機(jī)選取部分實際樣本且樣本達(dá)到一定數(shù)目的條件下，計算的概率能夠比較接近于真實結(jié)果。近似計算技術(shù)則需要合理構(gòu)建不確定數(shù)據(jù)的概率分布函數(shù)來計算概率的近似值，以此來最佳提升計算的效率，

11、如泊松分布近似計算方法。獨立樣本使用基本的蒙特卡羅方法產(chǎn)生，分值連續(xù)時，求解各種不確定性Top-K查詢時需要在聯(lián)合概率密度函數(shù)上進(jìn)行積分運算，使用馬爾可夫鏈的蒙特卡羅方法21，保證以高概率的方式取樣到有效的可能世界，提高近似程度。如MS-TopK查詢的蒙特卡羅取樣方法22、PT-K查詢的蒙特卡羅積分方法23、U-TopK查詢的動態(tài)馬爾可夫取樣方法24。綜上所述可知，確定性算法一般要比近似算法復(fù)雜程度高，而近似算法通過少量精度損失卻可大幅提升查詢效率。2分值與概率的平衡研究Li采用規(guī)范Kendall距離15對比同一數(shù)據(jù)集上的5種不確定性Top-K返回的結(jié)果，發(fā)現(xiàn)各語義返回結(jié)果差異顯著，有些結(jié)果甚

12、至完全相反。究其原因，主要有2點，分別是：記錄的概率和Ranking函數(shù)分值。通常有3種方式來處理分值和概率這兩大因素：1）先進(jìn)行分值排序再求取概率，如U-TopK。但是在利用分值求得所有的Top-K序列后，再將概率作為唯一的衡量標(biāo)準(zhǔn)，將導(dǎo)致弊端紛顯，因而應(yīng)將分值重新納入考量范疇。2）先求取概率，再進(jìn)行分值排序，如文獻(xiàn)5中指出在位置概率U-iRanks的基礎(chǔ)上根據(jù)Top-K位置上記錄的位置概率總和最大來進(jìn)行優(yōu)化，利用二分圖匹配的方式找出最優(yōu)排序。但是這種平衡方式可能使得到的結(jié)果序列在任何可能世界均不存在，并且也不是所有場景都能使用概率總和最大化目標(biāo)的求解方式。3）同時綜合考慮概率和排序，如gl

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

14、建等人25提出概率Skyline查詢的概念以檢索Skyline概率大于某個閾值的不確定對象，避免了用戶定義排序函數(shù)。但是可能導(dǎo)致無法控制返回結(jié)果的數(shù)目，因此，用戶還是需要設(shè)置具體概率閾值。為了解決概率閾值難于設(shè)置的問題，研究嘗試將Top-K查詢與其它查詢方式聯(lián)合起來，配置支持拓展開發(fā)。文獻(xiàn)26將Top-K查詢與Skyline相結(jié)合，提出概率Top-K支配（PTD）查詢的定義，使其具有Skyline查詢和概率排序查詢的優(yōu)點，能夠獲得針對某個查詢點具有最大支配能力的k個不確定對象。文獻(xiàn)27將傳統(tǒng)的聚集查詢與Top-K查詢相結(jié)合，提出排序-聚集查詢的概念，通過建?？臻g搜索問題、引入具有保證性的空間搜

15、索算法和流水線的處理框架，部分枚舉解空間快速獲得查詢結(jié)果。這種綜合多種查詢特征的新型查詢方式可以獲得多種查詢的優(yōu)勢，使得查詢結(jié)果更有利于實際應(yīng)用。3 結(jié)束語綜合國內(nèi)外不確定性Top-K查詢的研究現(xiàn)狀以及最新研究成果，如何開發(fā)高效的查詢處理方法、如何平衡分值與概率、如何設(shè)計滿足不同應(yīng)用環(huán)境的新型查詢語義依然是未來研究的重要方向。此外，由于很多現(xiàn)實應(yīng)用領(lǐng)域數(shù)據(jù)環(huán)境的不確定性和復(fù)雜性，例如分布式系統(tǒng)、高維數(shù)據(jù)庫、數(shù)據(jù)流等，使得在這種環(huán)境下的不確定性Top-K查詢正日趨現(xiàn)實具體與復(fù)雜。分布式系統(tǒng)中如何降低交互程度28-30、不確定數(shù)據(jù)流上Top-K查詢時間維的處理31-32、高維數(shù)據(jù)庫因維度提高而帶來

16、的Top-K語義變化和查詢效率問題將成為研究焦點。因此，分布式環(huán)境下不確定數(shù)據(jù)查詢方法33-34、基于流數(shù)據(jù)環(huán)境下不確定數(shù)據(jù)查詢方法35-37、基于高維數(shù)據(jù)庫的不確定查詢算法30，38-41亦可能成為未來持續(xù)研究熱點。Reference：1 蔣濤，高云君，張彬，等. 不確定數(shù)據(jù)查詢處理J. 電子學(xué)報，2013，41（5）：966-976.2 李文鳳， 彭智勇， 李德毅. 不確定性Top-K 查詢處理J. 軟件學(xué)報，2012，23（6）：1542-1560.3郭長友，鄭雪峰，高秀蓮. 基于不確定理論的不確定性數(shù)據(jù)Top-k查詢計算J. 計算機(jī)科學(xué).2016，43（3）：225-230. 4 SO

17、LIMAN M A， LLYAS I F， CHANG K C C. Top-K query processing in uncertain databasesC/IEEE International Conference on Data Engineering. Washington： IEEE Computer Society Press， 2007. 896-905.5 SOLIMAN M A， LLYAS I F. Ranking with uncertain scoresC/IEEE International Conference on Data Engineering. Wash

18、ington：IEEE Computer Society Press， 2009：317-328.6 LIAN L， CHEN L. Probabilistic ranked queries in uncertain databasesC/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 answersC/Pr

19、oceedings 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 databasesJ. Distributed and Parallel Databases， 2009， 26（1）：67-126.9 Hua M， Pei J， Zhang WJ， L

20、in XM. Ranking queries on uncertain data： A probabilistic threshold approachC/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 unce

21、rtain dataR/Burnaby：Simon Fraser University，2007.11 HUA M， PEI J. Ranking queries on uncertain dataJ. The VLDB Journal， 2011， 42（1）：9-32.12 CORMODE G， LI F， YI K. Semantics of ranking queries for probabilistic data and expected ranksC/IEEE International Conference on Data Engineering. Washington： IE

22、EE Computer Society Press， 2009， 23（12）：305-316.13 JESTES J， CORMODE G， LI F， et al. Semantics of ranking queries for probabilistic dataJ. 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 dataC /Proc of I

23、nt 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 databasesJ. The VLDB Journal， 2011，20（2）：249-275.16 LI J， DESHPANDE A. Ranking continuous probabilistic datasetsJ. Proceedings of the Vldb Endowment， 2010，3

24、（1-2）：638-649.17 YI K， LI F， KOLLIOS G， et al. Efficient processing of Top-k queries in uncertain databasesC/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 systemsC/IEEE International Conferen

25、ce 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 databasesJ. Journal of Distributed and Parallel Databases， 2009，26（1）：67-126.20 KARP R M，LUBY M.Monte-carlo algorithms for enumeration and reliability

26、 problemsC/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 dataJ.The VLDB Journal，2010，19（4）：477-501.22 RE C，DALVI N， SUCIU D. Efficient top-k query evaluation

27、 onprobabilistic dataC/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 dataJ.The VLDB Journal，2011，20（1）：129-153.24 SOLIMAN M A， LLYAS I F，CHANG C C.Probabilistic top-k and ranking-aggregate queriesJ.Acm Tra

28、nsactions on Database Systems，2008，33（3）：15-19.25 PEI J，JIANG B，LIN X，et al.Probabilistic skylines on uncertain dataC /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 databasesC / Proceedings of the 12t

29、h 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 queriesJ.ACM Trans on Database Systems（TODS）.2008，33（3）：15-19.28 WANG G， YUAN Y， SUN Y，

30、 et al. PeerLearning： A content-based e-learning material sharing system based on P2P networkJ. World Wide Web， 2011，13（3）：275-305.29 LI F， YI K， JESTES J. Ranking distributed probabilistic dataC/Acm Sigmod International Conference on Management of Data. Providence， RI， USA： ACM ， 2009：361-374.30 EL

31、-DESOUKY A/， ALI H/， ABDUL-AZEEM Y M. Ranking distributed uncertain database systems： Discussion and analysisC/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 streamsJ. The VLD

32、B Journal， 2010，19（3）：411-435.32 JIN C Q， GAO M， ZHOU A Y. Handling ER-Top K query on uncertain streamsM/ 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 dataC/Proceedings of the 2009 ACM SIGMOD International Conference on Management of data.Rhode Island，USA：ACM，2009：361-374.34 DING Xiaofeng，JIN Hai. Efficie