具有場(chǎng)境感知的概率Skyline查詢處理技術(shù)研究.pdf

1、隨著信息技術(shù)的發(fā)展和現(xiàn)實(shí)應(yīng)用需求的不斷擴(kuò)大，不確定數(shù)據(jù)已廣泛應(yīng)用于眾多的現(xiàn)實(shí)應(yīng)用中。近年來，概率Skyline查詢作為當(dāng)前不確定數(shù)據(jù)查詢研究的一個(gè)重要方面，已成為數(shù)據(jù)庫領(lǐng)域的一個(gè)研究熱點(diǎn)。然而傳統(tǒng)概率Skyline查詢結(jié)果通常與用戶的偏好相關(guān)，而用戶的偏好往往受當(dāng)前場(chǎng)境的影響，并且現(xiàn)實(shí)中的場(chǎng)境往往來源于感知設(shè)備，具有不確定性。論文研究了具有場(chǎng)境感知的概率Skyline查詢處理技術(shù)，主要工作和創(chuàng)新點(diǎn)如下：
　　(1)研究了不確定場(chǎng)境

2、下近似Skyline查詢處理技術(shù)，首次提出了不確定場(chǎng)境偏好可能世界語義建模下啟發(fā)式算法和基于Monte Carlo思想的近似Skyline查詢算法。首先，采用可能世界語義模型對(duì)不確定場(chǎng)境下偏好進(jìn)行建模，并提出不確定場(chǎng)境下Skyline查詢語義。其次，由于不確定場(chǎng)境下偏好構(gòu)成的可能世界實(shí)例過于龐大，精確Skyline算法ESA是＃P問題，提出LHSA和C&T兩種啟發(fā)式Skyline算法，從而大量裁減不滿足最終結(jié)果的可能世界實(shí)例。進(jìn)而，為了

3、在保證用戶指定精度的基礎(chǔ)上提高Skyline查詢效率提出了兩種Monte Carlo近似算法：兩階段Monte Carlo近似算法PMA和改進(jìn)的兩階段Monte Carlo近似算法MPMA。最后，通過實(shí)驗(yàn)對(duì)比5種算法，表明LHSA和C&T可以裁減大量可能世界實(shí)例，同時(shí)在確保精度的前提下，PMA和MPMA比啟發(fā)式算法更有效，并且MPMA算法優(yōu)于PMA算法。
　　(2)研究了不確定對(duì)象下的索引機(jī)制ZB*-tree。首先根據(jù)實(shí)例的Z-a

4、ddresses對(duì)實(shí)例進(jìn)行降序排列。Z-addresses通過對(duì)對(duì)象的每維采用二進(jìn)制表示能夠把多維對(duì)象映射到單維，進(jìn)而能夠?qū)Χ嗑S實(shí)例進(jìn)行排序。接著，根據(jù)排序的實(shí)例建立ZB*-tree索引。ZB*-tree索引是在ZBtree和B*-tree索引基礎(chǔ)上提出的一種新的內(nèi)存數(shù)據(jù)索引機(jī)制，通過ZB*-tree索引進(jìn)行概率Skyline查詢通過減少不確定對(duì)象或?qū)嵗g的支配比較，能夠降低查詢時(shí)間，提高概率Skyline查詢效率。
　　(3)

5、研究了不確定場(chǎng)境下概率Skyline查詢處理技術(shù)，計(jì)算不確定場(chǎng)境下不確定對(duì)象的精確Skyline概率。首先根據(jù)可能世界模型對(duì)不確定對(duì)象及不確定場(chǎng)境進(jìn)行建模，并提出了不確定場(chǎng)境下的概率Skyline查詢語義UC-PSkyline。然后根據(jù)ZB*-tree對(duì)不確定數(shù)據(jù)建立索引機(jī)制來避免重復(fù)支配比較，在此基礎(chǔ)上引進(jìn)預(yù)處理技術(shù)和剪枝策略機(jī)制，預(yù)處理技術(shù)能夠在建立索引之前確定Skyline概率為0或1的對(duì)象和實(shí)例，而剪枝策略機(jī)制能夠在UC-PSk