占美星 范少帥 周鵬

摘 要：針對(duì)不確定對(duì)象的最近鄰反向查詢沒有考慮多種特征類型而不能滿足復(fù)雜的應(yīng)用場景的問題，提出了基于限界剪枝和概率剪枝的多類型概率最近鄰反向（Multiple types probabilistic nearest neighbor reverse，MTPNNR）查詢算法。限界剪枝利用最小耗費(fèi)來修剪不可行解或者非最優(yōu)解對(duì)象;概率剪枝是基于概率分布模型和不確定對(duì)象分解的策略，根據(jù)概率各個(gè)閥值和剪枝的深度來控制需要剪枝的精度。與原始基于定義的算法相比較，MTPNNR查詢算法在CPU資源開銷方面有比較大的優(yōu)勢，能夠完成在較大數(shù)據(jù)復(fù)雜等環(huán)境下的查詢。基于實(shí)驗(yàn)結(jié)果顯示，MTPNNR算法在離散型的數(shù)據(jù)集和不確定數(shù)據(jù)集上有比較好的查詢效率。

關(guān)鍵詞：不確定對(duì)象;最近鄰反向查詢;概率剪枝;限界剪枝

1 緒論

在數(shù)據(jù)集中，其不確定性是一個(gè)比較新的領(lǐng)域，并且一直受到許多關(guān)注和研究。Lian等人于2009年首次提出了的LC算法，[1]在LC算法中第一次研究了PRNN問題，對(duì)于不確定對(duì)象LC算法采用了連續(xù)的概率密度函數(shù)來表示，該算法采用了數(shù)據(jù)集中的可能模型，對(duì)于數(shù)據(jù)集的不確定區(qū)域劃分為球形區(qū)域，當(dāng)查詢的結(jié)果大于該概率閥值則成為RNNs。

Cheema等人于2010年首次提出了CLWZP算法，[2]但該算法僅僅適合用于離散分布情況，并且采用了基于非平凡修建的規(guī)則和概率閥值的修剪算法，這樣能夠解決高維空間的不確定修剪不確定和收縮修剪區(qū)域的問題，比近似抽樣算法具有更高效和更具有擴(kuò)展性。

Emrich等人于2010年對(duì)MBRs的空間剪枝方法提出了最優(yōu)的研究方法，而Bernecker等人于2010年對(duì)概率近似性排序研究了相關(guān)算法，[4]該算法提出了概率剪枝法來加速排除不確定對(duì)象的相似。[5]基于這些前提的研究，Bernecker等人于2011深入研究了PNNR查詢，首次提出了概率修剪方法。[6]目前對(duì)確定數(shù)據(jù)集對(duì)象上多類型最近鄰反向查詢有一部分相關(guān)研究。[7-12]本文針對(duì)多個(gè)不同類型的不確定數(shù)據(jù)集對(duì)象，提出了MTPNNR查詢的概念，并基于離散型不確定數(shù)據(jù)集對(duì)象模型提出了MTPNNR查詢算法。

2 相關(guān)理論

2.1 基本概念

4.2 實(shí)驗(yàn)

本實(shí)驗(yàn)通過與base-MTPNNR算法相比較及逐步調(diào)整各輸入?yún)?shù)來驗(yàn)證MTPNNR算法的有效性。MTPNNR算法與base-MTPNNR算法相比，對(duì)于概率提純和過濾的上，采用了分層的概率剪枝，這樣大大節(jié)省了計(jì)算所有概率特征線路和所有不確定數(shù)據(jù)集的實(shí)例。

圖1比較了MTPNNR算法與base-MTPNNR算法的性能。如圖所示，當(dāng)FT=1時(shí)，其算法相差不大，查詢時(shí)間基本相等。圖2比較了基線算法和MTPNNR算法關(guān)于Ins查詢性能。

圖3描述了概率閥值對(duì)MTPNNR查詢的效率影響。從圖中可以看出MTPNNR的執(zhí)行時(shí)間是隨著τ值的增大而減小。這是由于較大的τ值會(huì)使互斥的最小概率1-τ的值減小，那么當(dāng)MTPNNR概率閥值增大時(shí)，其搜索空間對(duì)象相應(yīng)的隨著被修剪的概率1-τ減小而減少，所以在概率剪枝計(jì)算時(shí)，是很快找到所需的修剪閥值，是的增快了剪枝速度。

圖4-4是展示了MTPNNR算法對(duì)于Maxdep的查詢性能分析的結(jié)果，從圖中看到，隨著Maxdep增大，可以明顯的降低提煉步驟的CPU資源消耗。很顯然對(duì)于Maxdep來說，提煉步驟是主要的資源瓶頸，這是因?yàn)閷?duì)于較小的Maxdep值，每個(gè)在用于概率剪枝的不確定數(shù)據(jù)集對(duì)象的子區(qū)域集合是很小的，但是其分區(qū)很大。

經(jīng)過本次實(shí)驗(yàn)可知，MTPNNR算法的查詢性能是與各個(gè)輸入?yún)?shù)有直接的聯(lián)動(dòng)關(guān)系，并且實(shí)驗(yàn)結(jié)果驗(yàn)證了MTPNNR查詢算法的有效性，并且能夠在較合理的時(shí)間段內(nèi)完成相關(guān)查詢和剪枝。

5 結(jié)語

本文提出了多類型概率最近鄰反向查詢MTPNNR算法。并且針對(duì)MTPNNR查詢的需求，提出了SL-PFL和LL-PFL的特征概率修剪方法，從而整天提高了算法的空間查詢和剪枝效率。其次是運(yùn)用了限界剪枝方法，分層進(jìn)行剪枝，最后通過計(jì)算概率剪枝的上下界的方法進(jìn)行概率剪枝，最后通過實(shí)驗(yàn)，并且通過調(diào)整輸入?yún)?shù)使得MTPNNR查詢算法達(dá)到最優(yōu)，并且實(shí)驗(yàn)結(jié)果驗(yàn)證了MTPNNR算法的有效性，能為不確定數(shù)據(jù)集對(duì)象上的多類型概率最近鄰反向查詢提供有意義的參考。

參考文獻(xiàn)：

[1]Lian X，Chen L.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data[J].The VLDB Journal，2009，18（3）：787-808.

[2]Cheema M A，Lin X，Wang W，et al.Probabilistic reverse nearest neighbor queries on uncertain data[J].IEEE Transactions on Knowledge and Data Engineering，2010，22（4）：550-564.

[3]Emrich T，Kriegel H P，Kroger P，et al.Boosting spatial pruning：On optimal pruning of MBRs[C].Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.New York：ACM Press，2010：39-50.

[4]Bernecker T，Kriegel H P，Mamoulis N，et al.Scalable probabilistic similarity ranking in uncertain databases[C].Proceedings of IEEE Transactions on Knowledge and Data Engineering.[s.l.]：TKDE Press，2010：1234-1246.