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

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

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

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

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

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

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

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