基于不確定數(shù)據(jù)的范圍查詢算法的研究與實現(xiàn).pdf

1、隨著計算機技術(shù)的不斷發(fā)展，現(xiàn)實生活開始頻繁出現(xiàn)類似于無線射頻識別(RFID)，GPS導(dǎo)向，無線傳感器，雷達(dá)測速等實際應(yīng)用。由于信息采集技術(shù)，信息存儲等客觀因素的限制以及儀器設(shè)備精密度的限制，導(dǎo)致了不確定數(shù)據(jù)的產(chǎn)生。不確定數(shù)據(jù)固有的不確定性使得在管理不確定數(shù)據(jù)時引入了概率的需求，概率可以較準(zhǔn)確的描述不確定數(shù)據(jù)的屬性相關(guān)值。所以，盡管傳統(tǒng)的數(shù)據(jù)庫管理技術(shù)已達(dá)到比較成熟的階段，但由于沒有考慮概率需求，傳統(tǒng)的數(shù)據(jù)管理技術(shù)已不再適用于不確定數(shù)據(jù)，

2、這對數(shù)據(jù)庫理論與技術(shù)提出了新的挑戰(zhàn)。目前，雖然不確定數(shù)據(jù)通常都采用概率數(shù)據(jù)模型表示，較強的表示了不確定數(shù)據(jù)間的相關(guān)性，但在查詢與概率推理方面其時間復(fù)雜度相對過高。所以，研究一個能支持不確定數(shù)據(jù)的高效索引和快速查詢算法是當(dāng)前的重點也是熱點問題。
　　本文針對不確定數(shù)據(jù)查詢問題，進(jìn)行了一定的分析與研究。首先，提出了一種新的索引結(jié)構(gòu)S-Box來管理不確定數(shù)據(jù)。這種結(jié)構(gòu)可以有效地支持基于概率數(shù)據(jù)的范圍查詢。S-Box是一種由R-tree改

3、進(jìn)而來的樹型結(jié)構(gòu)。在索引結(jié)構(gòu)中，主要記錄本論文提出的一種新的框架——skeleton。在S-Box的每個節(jié)點中，都記錄了一組skeleton，它可以在空間上為查詢提供一個非常緊湊的邊界約束bound，以至于可以過濾掉與查詢區(qū)域沒有重疊的部分對象，減少查詢的訪問代價和時間開銷，提高查詢速度。
　　其次，提出一種新的數(shù)據(jù)結(jié)構(gòu)BBD+-tree管理不確定數(shù)據(jù)對象。BBD+-tree采用多分辨率網(wǎng)格很好的刻化了對象的概率密度函數(shù)，在概率上

4、為查詢提供了緊湊的bound。
　　再者，基于S-Box的索引結(jié)構(gòu)，提出了兩種查詢算法對不確定數(shù)據(jù)進(jìn)行范圍查詢。算法SBO利用S-Box返回出現(xiàn)在一個查詢區(qū)域內(nèi)的概率大于某一概率閾值的不確定數(shù)據(jù)對象。算法中用到了骨架skeleton和剪枝策略，使得查詢可以大范圍的減小搜索空間和計算開銷，從而提高查詢速度和效率。進(jìn)一步，提出了SBO算法的優(yōu)化算法SCFB，算法的基本思想與SBO基本一樣，不同的是文章設(shè)計了一個過濾器CF，這個過濾器C

5、F用在訪問對象對應(yīng)的BBD+-tree之前。如果對象可以通過CF直接被剪枝掉，則就不需要訪問BBD+-tree，減少了訪問BBD+-trree的時間開銷，否則，需要繼續(xù)訪問BBD+-tree。SCFB算法進(jìn)一步在時間開銷上進(jìn)行了優(yōu)化，使得查詢更加快速有效。
　　最后，為了分析驗證S-Box結(jié)構(gòu)以及相關(guān)算法的性能優(yōu)勢，本文做了大量的比對試驗。通過與典型的U-Tree，UD-Tree進(jìn)行實驗比對分析，實驗結(jié)果表明，本文提出的索引結(jié)構(gòu)和