動態(tài)k值聚類的R-樹空間索引構建.pdf

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

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

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