移動計算環(huán)境下非確定數(shù)據(jù)的索引與查詢方法研究.pdf

1、在移動對象數(shù)據(jù)庫的研究中，如何建模、索引并查詢移動對象的位置信息是一個很重要的問題，學(xué)者們對此進(jìn)行了大量研究，并提出了許多空間對象和時空對象的索引方法。但是傳統(tǒng)的方法并不能支持此類數(shù)據(jù)的一個重要應(yīng)用特性——非確定性，如何對非確定性數(shù)據(jù)進(jìn)行查詢處理成了數(shù)據(jù)庫研究人員關(guān)注的焦點。在移動計算環(huán)境中，受限于測量設(shè)備誤差，數(shù)據(jù)更新延遲，取樣失真等因素，中心數(shù)據(jù)庫很難全程記錄移動對象的準(zhǔn)確位置信息，鑒于傳統(tǒng)的移動對象索引方法和查詢處理技術(shù)均假設(shè)數(shù)據(jù)

2、庫中的數(shù)據(jù)是精確的，因此這些技術(shù)不能直接應(yīng)用到非確定數(shù)據(jù)的索引和查詢，或者效率極低，這就給研究者提出了新的問題和挑戰(zhàn)。
　　 U 樹是具有代表性的一種非確定對象空間索引方法，它是在R*樹基礎(chǔ)之上融合了數(shù)據(jù)非確定性的變種。U 樹固有的良好動態(tài)結(jié)構(gòu)，這使它不僅可以支持非確定數(shù)據(jù)對象以任何次序更新或插入，而且其提出的域查詢處理算法不局限于非確定數(shù)據(jù)本身的概率密度分布函數(shù)。但U 樹本身只是針對非確定靜止對象的索引，并不能支持非確定移動對

3、象的索引或執(zhí)行效率甚微。
　　 基于移動計算環(huán)境，針對如何支持頻繁位置更新的非確定移動對象當(dāng)前及未來位置索引的問題，在基本U 樹結(jié)構(gòu)上增加了記錄移動對象非確定狀態(tài)特征的數(shù)據(jù)結(jié)構(gòu)，通過利用概率密度分布函數(shù)描述移動對象在非確定區(qū)域的位置分布，在保留原有位置記錄的情況下加入時間特性，這樣就可以預(yù)測移動對象在未來時間段內(nèi)的大概位置信息，從而為當(dāng)前及未來非確定位置信息檢索提供可靠保證。在TPU 樹索引基礎(chǔ)上，一種改進(jìn)的基于p-bound的

4、域查詢處理算法MP_BBRQ，利用索引中記錄的概率限定性區(qū)域和啟發(fā)式判定準(zhǔn)則，能高效的處理概率性域查詢問題；一種基于分支定界思想的概率skyline 查詢處理算法B 2 CPS，利用最近鄰的最好優(yōu)先遍歷思想，能使查詢處理的磁盤開銷達(dá)到最優(yōu)。
　　 相對于傳統(tǒng)的空間查詢概念，非確定數(shù)據(jù)庫中常用的查詢——概率空間查詢，由于其結(jié)果集中增加了結(jié)果正確性的保證系數(shù)，從而使得基于非確定數(shù)據(jù)的查詢更具有可信性。鑒于概率空間查詢具有很高的計算代

5、價，需要進(jìn)一步提高概率空間查詢效率，尤其是旨在減少CPU計算時間和磁盤I/O 次數(shù)的概率k 最近鄰查詢算法，國內(nèi)外目前尚無相關(guān)研究。概率k 最近鄰查詢k-PNN 就是返回k個非確定對象，而且這k個非確定對象分別作為查詢對象Q的第k個最近鄰居的概率，相對于其它非確定對象是最大的。與傳統(tǒng)的k 最近鄰查詢相比，計算非確定對象的k 最近鄰概率值需要原始的積分運算或Monte-Carlo方法，在這種情況下，概率k 最近鄰查詢的計算代價是非常高的。

6、因此，必須盡量縮小查詢所需搜索的空間范圍，從而在不影響返回正確結(jié)果集的情況下，進(jìn)一步減少所要考慮的非確定對象，在很大程度上避免利用原始計算公式來返回結(jié)果集。高效處理k-PNN 查詢框架包含四個步驟：R 樹索引的建立，空間裁剪，概率裁剪和精煉階段。利用安全可靠的空間裁剪以及概率裁剪方法，把這些方法與R 樹索引進(jìn)行完美的結(jié)合以減少查詢的搜索空間，從而提高k-PNN 查詢的處理效率。實驗結(jié)果表明，空間裁剪和概率裁剪方法具有非常高的裁剪效率，整

7、個k-PNN 查詢處理過程是可靠高效的。
　　 非確定數(shù)據(jù)庫需要研究的問題還很多，在許多查詢問題上欠缺高效的處理算法，例如概率連接問題，概率Top-k 查詢，概率反最近鄰查詢，以及概率反輪廓查詢等等，因此，針對不同方面的概率空間和時空查詢問題，將相應(yīng)解決方法融入到數(shù)據(jù)庫管理系統(tǒng)中以支持非確定數(shù)據(jù)的有效管理，將是研究人員面臨的新問題。此外，將已有的研究成果應(yīng)用于多維空間，并進(jìn)一步考慮非歐式距離環(huán)境下的索引及查詢處理方法可作為未來的