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

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

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

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