基于不確定數據的范圍查詢算法的研究與實現.pdf

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

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

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

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

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