基于R-樹空間索引的研究.pdf

1、近年來，空間數(shù)據(jù)庫索引的研究引起了人們越來越多的興趣和關注，其中1984年Guttman提出的R-樹是目前最流行的動態(tài)空間索引結構，廣泛應用于原型研究和商用空間數(shù)據(jù)庫系統(tǒng)。 R-樹是一種層次數(shù)據(jù)結構，是B-樹在k維空間上的自然擴展。近年來，許多學者致力于R-樹的研究，在R-樹的基礎上衍生出了許多變種，比較典型的有R+樹，壓縮R-樹等?；赗-樹索引結構需要解決的主要問題仍然是減少區(qū)域的重疊，提高搜索效率。從而確立本論文的研究內

2、容： 本文首先從空間數(shù)據(jù)特征和空間檢索出發(fā)，系統(tǒng)地總結常用的空間索引技術，如KDB-樹、R-樹及其變種等。重點介紹R-樹的定義、查找、插入及刪除算法。 通過對基于四叉樹的空間索引技術的研究，深入分析基于四叉樹和R-樹的空間索引結構-QR-樹，與R-樹相比，QR-樹以略大（有時甚至略?。┑目臻g開銷代價換取更高的性能，且索引目標數(shù)越多，QR-樹的整體性能越好。 然后一般空間聚類的定義出發(fā)，將k-均值聚類算法引入R-樹

3、的生成算法中，提出一種R-樹結點分配的新算法。該算法定義了空間實體間距離的計算方法，與原始算法相比，產(chǎn)生的交疊會更小，從而有效的控制多路查詢的幾率，較明顯的提高了空間查詢的效率。 最后針對空間數(shù)據(jù)的特點和R-樹的性能對傳統(tǒng)的k-均值聚類算法進行改進和擴充，提出R-樹生成的新算法，該算法對均勻分布和非均勻分布的空間對象都能給出很好的R-樹生成。提出QROO-樹，此結構針對現(xiàn)有的四叉樹和R-樹的空間索引結構中存在的問題，采用面向對象