動(dòng)態(tài)k值聚類(lèi)的R-樹(shù)空間索引構(gòu)建.pdf

1、空間信息技術(shù)的日益發(fā)展與位置服務(wù)需求的不斷增長(zhǎng)，使得空間數(shù)據(jù)的管理成為當(dāng)前空間信息研究領(lǐng)域的熱點(diǎn)?？臻g數(shù)據(jù)具有數(shù)據(jù)量龐大、結(jié)構(gòu)復(fù)雜、數(shù)據(jù)之間具有位置關(guān)聯(lián)性的特點(diǎn)，加之對(duì)位置服務(wù)質(zhì)量和檢索速度要求的提高，需要恰當(dāng)?shù)亟M織它們，以便高效地管理、存儲(chǔ)和分析空間數(shù)據(jù)。
　　采用索引技術(shù)組織空間數(shù)據(jù)，可以在檢索時(shí)快速定位到指定位置，提高檢索速度。R-樹(shù)空間索引是當(dāng)前主流的空間索引技術(shù)，它結(jié)構(gòu)簡(jiǎn)明、適用范圍廣、動(dòng)態(tài)性高，在構(gòu)建過(guò)程中通常有三種方

2、式——OBO（One by one）方式、預(yù)處理方式和聚類(lèi)方式。OBO方式插入代價(jià)大、節(jié)點(diǎn)間交疊程度高；預(yù)處理方式降低了節(jié)點(diǎn)間交疊程度和構(gòu)建復(fù)雜度，但不是按照空間實(shí)際分布構(gòu)建；聚類(lèi)方式利用聚類(lèi)算法劃分空間數(shù)據(jù)，盡可能把相近的空間數(shù)據(jù)組織在同一子樹(shù)下，從整體上提高了索引效率。但是，目前采用的R-樹(shù)空間聚類(lèi)技術(shù)使用指定 k值的聚類(lèi)算法，初始聚類(lèi)中心隨機(jī)或指定選取。這樣聚類(lèi)的結(jié)果受初始k值影響，且易受離群空間數(shù)據(jù)的干擾。
　　針對(duì)這一問(wèn)

3、題，本文在比較當(dāng)前主流空間索引技術(shù)優(yōu)缺點(diǎn)的基礎(chǔ)上，以靜態(tài)空間數(shù)據(jù)為對(duì)象，結(jié)合空間數(shù)據(jù)的實(shí)際分布，提出動(dòng)態(tài)確定 k值的空間聚類(lèi)算法（DynamicK-value Spatial Clustering Algorithm，DKSC）。該算法通過(guò)聚類(lèi)劃分空間數(shù)據(jù)，把同一子空間的數(shù)據(jù)組織在同一子樹(shù)下，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐層構(gòu)建R-樹(shù)，形成高效的R-樹(shù)空間索引。在構(gòu)建完成之后，利用一種輔助結(jié)構(gòu)實(shí)現(xiàn)對(duì)空間數(shù)據(jù)的高效批量插入。分別用百度地圖API生成