基于Chameleon聚類算法的R樹索引方法研究.pdf

1、隨著GIS技術(shù)的快速發(fā)展，空間數(shù)據(jù)庫在各個領(lǐng)域都得到了極大的發(fā)揮，其主要的任務(wù)是對空間數(shù)據(jù)實(shí)現(xiàn)有效的存儲，進(jìn)而實(shí)現(xiàn)高效訪問的目的?？臻g數(shù)據(jù)具有海量性、內(nèi)部結(jié)構(gòu)復(fù)雜性、屬性多樣性等特征，如何有效的對數(shù)據(jù)進(jìn)行存儲，是當(dāng)前空間數(shù)據(jù)庫領(lǐng)域的一個難點(diǎn)問題。R樹索引結(jié)構(gòu)能夠?qū)Ω呔S海量空間數(shù)據(jù)實(shí)施有效的存儲，且數(shù)據(jù)之間仍具有物理空間中的鄰近性，主要應(yīng)用于商業(yè)數(shù)據(jù)庫中。
　　針對當(dāng)前R樹索引結(jié)構(gòu)存在的不足，本文主要按照以下三個部分進(jìn)行研究:

2、>　　首先，針對傳統(tǒng)R樹構(gòu)建以及分裂方法的不足，本文結(jié)合Chameleon聚類算法對其進(jìn)行預(yù)處理，實(shí)現(xiàn)一種批量生成索引結(jié)構(gòu)的技術(shù)。利用聚類結(jié)果中簇內(nèi)相似性高，簇間相似性低的特點(diǎn)，可以減小節(jié)點(diǎn)的MBR(最小外包矩形)面積以避免重疊，提高算法的效率。經(jīng)聚類后的節(jié)點(diǎn)之間相似性較低，查詢過程中避免多路徑檢索，提高查詢效率。
　　其次，針對Chameleon算法的時間復(fù)雜度較高，通過人工蜂群方法得到一次聚類之后的質(zhì)心，并作為下次聚類的初始解

3、。利用K-means算法進(jìn)行下次聚類，有效避免了任意初始值和噪聲點(diǎn)對R樹節(jié)點(diǎn)的影響，同時減少了構(gòu)建索引結(jié)構(gòu)的時間，使得靜態(tài)R樹在處理大數(shù)據(jù)過程中具備伸縮性。
　　最后，針對不確定數(shù)據(jù)存儲復(fù)雜的問題，本文結(jié)合聚類算法和Hilbert曲線降維方法，利用最大最小矩形剪枝策略，減少算法中積分的運(yùn)算量，提高構(gòu)建Hilbert-R樹的效率。使用Chameleon聚類算法可以使數(shù)據(jù)之間更加緊湊，可以使除根節(jié)點(diǎn)以外的數(shù)據(jù)都是滿容量的，提升了節(jié)點(diǎn)的