吳明光

南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210023

1 引 言

隨著空間數(shù)據(jù)采集技術(shù)的發(fā)展，逐項(xiàng)（one by one，OBO）裝載、插入待索引對(duì)象的空間索引難以滿足海量、動(dòng)態(tài)空間數(shù)據(jù)的查詢管理需求［1］。支持批量操作的空間索引成為當(dāng)前的研究熱點(diǎn)之一［2］。

從空間索引的構(gòu)建方式來(lái)講，支持批量操作的索引主要包括自上（根節(jié)點(diǎn)）而下（葉子節(jié)點(diǎn)）、自下而上兩種方式。自上而下的批量處理方式中比較典型的是 TGS R 樹(shù)［3］、OMT［4］、Merging R樹(shù)（small tree large tree，STLT）［5］、GBI［6］、SCB［7］。TGS R樹(shù)對(duì)數(shù)據(jù)進(jìn)行遞歸二路劃分，自上而下構(gòu)建索引樹(shù)。OMT采用最小化節(jié)點(diǎn)重疊度的空間劃分方法將空間進(jìn)行遞歸劃分，自上而下遞歸構(gòu)建索引樹(shù)。Merging R樹(shù)首先根據(jù)待索引對(duì)象構(gòu)建小的索引樹(shù)，再將小的索引樹(shù)整體插入大的索引樹(shù)中去。聚類方法也被引入空間索引時(shí)的節(jié)點(diǎn)劃分中［8］。GBI采用k－means聚類將數(shù)據(jù)集劃分為多個(gè)組群和離群值，一個(gè)組群建立一顆單獨(dú)的索引樹(shù)，反復(fù)采用STLT來(lái)構(gòu)建索引樹(shù)。SCB方法也將插入數(shù)據(jù)分為聚類數(shù)據(jù)與離群數(shù)據(jù)。與STLT不同的是，SCB依據(jù)第k層節(jié)點(diǎn)的最小外接矩形（minimum bounding rectangle，MBR）對(duì)插入的數(shù)據(jù)進(jìn)行聚類。TGS R樹(shù)、OMT方法面向數(shù)據(jù)的批量加載，批量插入效率不高。STLT、GBI、SCB試圖構(gòu)建小的索引樹(shù)，將小的索引樹(shù)整體插入基態(tài)索引樹(shù)中。

自下而上的批量處理主要包括排序、聚類與Buffer樹(shù)［9］等方法。lowx packed R 樹(shù)［10］通過(guò)對(duì)MBR角點(diǎn)的x或者y坐標(biāo)排序、分組，一次一層構(gòu)建整個(gè)樹(shù)。Hilbert Pack R樹(shù)［11］引入空間填充曲線來(lái)改進(jìn)lowx Packed R樹(shù)中的排序方法。STR樹(shù)［12］采用遞歸網(wǎng)格排序方法，以劃分矩形為建樹(shù)單位，自下而上一次一層生成整個(gè)索引樹(shù)。k－way R 樹(shù)［13］引入 k－means聚類方法對(duì)數(shù)據(jù)進(jìn)行聚類，一個(gè)聚類對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，自下而上構(gòu)建整個(gè)樹(shù)。Buffer樹(shù)將空間索引樹(shù)結(jié)構(gòu)關(guān)聯(lián)一個(gè)基于緩存的臨時(shí)數(shù)據(jù)結(jié)構(gòu)，批量構(gòu)建整個(gè)樹(shù)。自下而上的構(gòu)建方法能夠顯著提高索引構(gòu)建效率而且能夠保證查詢性能，但均需要數(shù)據(jù)集的整體信息，適用于靜態(tài)數(shù)據(jù)。

不管是自上而下還是自下而上的空間索引方法，均存在兩個(gè)難點(diǎn)：①批量操作的基本粒度的定義；②局部更新操作對(duì)索引樹(shù)的整體影響。lowx packed R等將排序、分組的結(jié)果作為批量操作的基本單元。該類方法不適用于具體復(fù)雜幾何形態(tài)的線、面對(duì)象。GBI、k－way R樹(shù)等采用聚類方法來(lái)定義批量操作基本單元的方法也存在不足。首先，均勻分布的數(shù)據(jù)沒(méi)有聚類前提。其次，劃分聚集分布的數(shù)據(jù)時(shí)容易出現(xiàn)數(shù)據(jù)傾斜現(xiàn)象；Merging R樹(shù)方法試圖通過(guò)小索引樹(shù)整體插入大索引樹(shù)的方法來(lái)解決索引樹(shù)的批量更新問(wèn)題。但是，將小索引樹(shù)插入基態(tài)索引樹(shù)的過(guò)程中依然需要解決插入后節(jié)點(diǎn)間的空間重疊度調(diào)整等問(wèn)題。而且，小索引樹(shù)的構(gòu)建參數(shù)需要與基態(tài)索引樹(shù)的構(gòu)建參數(shù)完全匹配。Buffer樹(shù)引入緩存機(jī)制僅能延遲索引樹(shù)的整體更新，不能避免局部更新帶來(lái)的整體重構(gòu)。

本文以空間分布模式作為索引樹(shù)構(gòu)建的切入點(diǎn)，針對(duì)難點(diǎn)1，提出基于空間分布模式探測(cè)的空間數(shù)據(jù)劃分方法，設(shè)計(jì)自上而下與自下而上相結(jié)合的索引樹(shù)構(gòu)建方法。針對(duì)難點(diǎn)2，則采用基于空間分布模式變化檢測(cè)的索引更新方法。

2 Pattern－tree結(jié)構(gòu)描述

空間劃分方法是樹(shù)狀空間索引的核心問(wèn)題之一，其附帶的問(wèn)題包括劃分區(qū)域的重疊度、劃分區(qū)域的數(shù)據(jù)量均衡以及同組對(duì)象的空間鄰近性等?？臻g劃分與聚類相同點(diǎn)都是為了維護(hù)組內(nèi)對(duì)象相似、組間對(duì)象相離。與聚類不同的是，空間索引中的空間劃分還需要考慮組間對(duì)象數(shù)據(jù)量均衡、組間空間重疊度最小、組間查詢效率均衡等。文獻(xiàn)［14］已經(jīng)證明多目標(biāo)的空間劃分問(wèn)題是一個(gè)NP完全問(wèn)題。本文不試圖給出空間劃分的多目標(biāo)求解方法，而是結(jié)合Hilbert空間填充曲線和空間分布模式分析方法，提出一種同時(shí)顧及空間鄰近、分組數(shù)據(jù)量、組間空間重疊度等條件的空間數(shù)據(jù)劃分方法。Hilbert曲線具有很好的空間鄰近性，能夠保證Hilbert編碼連續(xù)的實(shí)體在空間上的最大程度的鄰近［15］。但是Hilbert曲線用于空間索引構(gòu)建還存在3個(gè)問(wèn)題：①Hilbert曲線某種程度上反映了空間鄰近性，但沒(méi)有直接反映數(shù)據(jù)的空間分布模式?？臻g分布模式直接決定了空間劃分的組間空間重疊度、數(shù)據(jù)量均衡、同組對(duì)象的空間鄰近性，間接決定了葉子節(jié)點(diǎn)的扇入、扇出度與葉子節(jié)點(diǎn)查詢操作的負(fù)載平衡；②Hilbert曲線與Rn空間之間并非雙向映射，空間上鄰近的對(duì)象其Hilbert編碼不一定鄰近，僅依據(jù)Hilbert編碼來(lái)進(jìn)行數(shù)據(jù)劃分，可能帶來(lái)硬分割而破壞組內(nèi)對(duì)象的空間聚集性；③Hilbert曲線能夠一定程度上反映空間數(shù)據(jù)的聚集程度，但無(wú)法直接反映一組Hilbert編碼相同或者相近的空間數(shù)據(jù)內(nèi)部的離散程度。同組對(duì)象之間的離群值將降低組內(nèi)數(shù)據(jù)的聚集程度，可能會(huì)導(dǎo)致組間出現(xiàn)大范圍的空間重疊，帶來(lái)空間查詢時(shí)的多路徑搜索。

如圖1所示，本文采用Hilbert空間填充曲線對(duì)索引對(duì)象進(jìn)行編碼。針對(duì)問(wèn)題①，引入空間模式分析方法對(duì)索引對(duì)象進(jìn)行空間模式分析，將其進(jìn)行空間劃分，得到組內(nèi)相似、組間相異、組間數(shù)據(jù)量均衡的數(shù)據(jù)塊，稱之為Pattern。針對(duì)問(wèn)題②、③，如圖1（a）所示，提出一種 Hilbert編碼異常值的檢測(cè)方法，將Pattern中的對(duì)象劃分為正常值和異常值（可能存在0個(gè)或者多個(gè)異常值，具體定義與算法描述詳見(jiàn)3.1）。以Pattern作為空間索引樹(shù)葉子節(jié)點(diǎn)的構(gòu)建單位，由下至上，一次一層，批量構(gòu)建空間索引樹(shù)Pattern－tree見(jiàn)圖1（b）。對(duì)異常值則采用自上而下的方式進(jìn)行：從根節(jié)點(diǎn)開(kāi)始，遍歷索引節(jié)點(diǎn)，如果將異常值插入某個(gè)節(jié)點(diǎn)后，該節(jié)點(diǎn)的最小外接矩形變化最小，則將該節(jié)點(diǎn)作為插入節(jié)點(diǎn)。如果該節(jié)點(diǎn)不是數(shù)據(jù)節(jié)點(diǎn)，則繼續(xù)遍歷其子節(jié)點(diǎn)，直到異常值插入數(shù)據(jù)節(jié)點(diǎn)中。

圖1 Pattern－tree構(gòu)建示意圖Fig.1 Schematic diagram of Pattern－tree

與四叉樹(shù)［16］、R 樹(shù)［17］等在索引樹(shù)結(jié)構(gòu)上相同的是，Pattern－tree包括根節(jié)點(diǎn)、索引節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)。根節(jié)點(diǎn)，全局唯一，可以包括若干索引節(jié)點(diǎn)。索引節(jié)點(diǎn)可以包括索引節(jié)點(diǎn)或者數(shù)據(jù)節(jié)點(diǎn)。數(shù)據(jù)節(jié)點(diǎn)處于索引樹(shù)的最底層，包含若干索引對(duì)象（見(jiàn)圖1（c））。數(shù)據(jù)節(jié)點(diǎn)可描述為（I，tuple－identifier），其中，tuple－identifier表示一個(gè)n維的待索引對(duì)象，I是這個(gè)葉子結(jié)點(diǎn)中所有待索引對(duì)象的最小外接矩形。索引節(jié)點(diǎn)可描述為（I，child－pointer），其中，child－pointer是指向子節(jié)點(diǎn)的指針，I是覆蓋所有子結(jié)點(diǎn)的最小外接矩形［16］。Pattern－tree是平衡樹(shù)，任意對(duì)象離根節(jié)點(diǎn)的距離相等，查詢期望值相等。與其他索引在結(jié)構(gòu)上不同的是，節(jié)點(diǎn)容量與溢出處理方面，R樹(shù)完全依賴于節(jié)點(diǎn)的容量，節(jié)點(diǎn)填充度為50%［17］，達(dá)到上限則觸發(fā)節(jié)點(diǎn)分裂，達(dá)到下限則觸發(fā)節(jié)點(diǎn)合并。由于空間分布本身的不均勻，由數(shù)據(jù)量驅(qū)動(dòng)的節(jié)點(diǎn)分裂和合并操作容易產(chǎn)生高空間重疊度而帶來(lái)的低效空間索引。Pattern－tree放棄數(shù)據(jù)驅(qū)動(dòng)而采用空間分布模式驅(qū)動(dòng)，以Pattern作為節(jié)點(diǎn)，Pattern僅設(shè)定數(shù)據(jù)量上限。

索引樹(shù)平衡性與索引樹(shù)高度方面，KD樹(shù)［18］、四叉樹(shù)為非平衡樹(shù)，數(shù)據(jù)節(jié)點(diǎn)的深度因空間數(shù)據(jù)分布不同，可能會(huì)有較大的差異。如在數(shù)據(jù)密度較大的區(qū)域數(shù)據(jù)節(jié)點(diǎn)較深，密度較小的區(qū)域數(shù)據(jù)節(jié)點(diǎn)較淺。KD樹(shù)在最壞的情況下，n個(gè)對(duì)象的KD樹(shù)的高度為n［18］。文獻(xiàn)［19］給出了R樹(shù)高度計(jì)算公式

式中，N為數(shù)據(jù)記錄總數(shù)；ci為節(jié)點(diǎn)容量；f為節(jié)點(diǎn)平均容量。Pattern－tree包括數(shù)據(jù)節(jié)點(diǎn)、索引節(jié)點(diǎn)兩個(gè)容量參數(shù)。本文給出Pattern－tree高度計(jì)算公式為

式中，N、f參數(shù)同R樹(shù)；Ci為索引節(jié)點(diǎn)容量；Cd為數(shù)據(jù)節(jié)點(diǎn)容量。R樹(shù)依據(jù)節(jié)點(diǎn)容量進(jìn)行節(jié)點(diǎn)分裂與樹(shù)的生長(zhǎng)，Pattern－tree則同時(shí)依據(jù)索引節(jié)點(diǎn)容量和數(shù)據(jù)組群分布進(jìn)行節(jié)點(diǎn)分裂與樹(shù)的生長(zhǎng)。易知，當(dāng)索引節(jié)點(diǎn)容量相等時(shí)，若數(shù)據(jù)節(jié)點(diǎn)容量小于索引節(jié)點(diǎn)容量，Pattern－tree的高度要小于R樹(shù)的高度，能有效減小索引路徑的長(zhǎng)度。若節(jié)點(diǎn)分裂算法和節(jié)點(diǎn)訪問(wèn)參數(shù)相同，則能有效提高搜索效率。Pattern－tree中索引節(jié)點(diǎn)容量Ci反映組群的個(gè)數(shù)，數(shù)據(jù)節(jié)點(diǎn)容量Cd反映對(duì)象的個(gè)數(shù)，具有明確的數(shù)據(jù)含義，容易根據(jù)不同類型的數(shù)據(jù)來(lái)定義容量值。

3 Pattern－tree關(guān)鍵算法

3.1 基于空間模式分析方法的空間數(shù)據(jù)劃分

本文采用文獻(xiàn)［19］中的分散性指數(shù)來(lái)判斷空間分布類型。若實(shí)體呈規(guī)則分布或者隨機(jī)分布，則采用等間隔劃分與離群值調(diào)整的方法獲得分組結(jié)果；若實(shí)體呈聚集分布，則進(jìn)行迭代尋優(yōu)獲得分組結(jié)果。

本文將問(wèn)題①、②中出現(xiàn)的離群值和非正常值統(tǒng)稱為異常值，與之對(duì)應(yīng)的則稱為正常值。本文采用Hilbert編碼與距離的半變異函數(shù)來(lái)區(qū)分異常值與正常值。如式（3）所示，半變異函數(shù)（空間距離的函數(shù)）將Hilbert編碼的方差作為變量

式中，d表示空間距離；N（d）表示距離為d的數(shù)據(jù)對(duì)（pair）的個(gè)數(shù)；Hi表示第i個(gè)對(duì)象的Hilbert編碼；Hi＋d表示距離第i個(gè)對(duì)象為d的某個(gè)對(duì)象的Hilbert編碼。

依據(jù)式（3），空間距離較小，Hilbert編碼差異較大的點(diǎn)（見(jiàn)圖2中A）所對(duì)應(yīng)的半變異函數(shù)值較大；空間距離較大，Hilbert編碼也不同的點(diǎn)（見(jiàn)圖2中B）所對(duì)應(yīng)的半變異函數(shù)值也較大。通過(guò)半變異函數(shù)值可尋找到離群值。

對(duì)于離群值，本文定義了一個(gè)反映組內(nèi)對(duì)象聚集特征的目標(biāo)函數(shù)來(lái)進(jìn)行調(diào)整。如式（4）所示，本文將聚集特征描述為組內(nèi)對(duì)象Hilbert離差平方和（Et）和組間離差平方和（E）兩個(gè)指標(biāo)。

圖2 異常值示意圖Fig.2 An examples dataset with outliers

式中，k為分組個(gè)數(shù)；t為組別標(biāo)識(shí)；nt表示第t組對(duì)象個(gè)數(shù)；ht為t組Hilbert碼均值；hi為t組第i個(gè)Hilbert碼。

聚集分布的數(shù)據(jù)空間劃分的具體步驟是：

（1）首先對(duì)SH進(jìn)行自然裂點(diǎn)劃分，將整個(gè)集合分 解 為k個(gè) 組，SH＝｛g1，g2，…，gn｝，0＜n＜k。計(jì)算Et和E。

（2）對(duì)（1）得到的分組gn，嘗試將離群對(duì)象hi置入其他分組，并同時(shí)比較E值。若將hi置入gm后，E減少最多，則將hi置入gm，完成一次組內(nèi)離群對(duì)象調(diào)整。若E不變，則將hi置入對(duì)象個(gè)數(shù)較小的一個(gè)分組（數(shù)據(jù)量補(bǔ)償策略）。

（3）對(duì)k個(gè)組分別進(jìn)行離群值調(diào)整，完成一次整體迭代。

（4）重復(fù)進(jìn)行（3），直至E不再減少。

Hilbert碼的鄰近性間接反映了實(shí)體之間的空間鄰近性與聚集特征，因此該方法能夠顧及實(shí)體之間的空間聚集特征；在離差平方和相等的情況下，采用數(shù)據(jù)量補(bǔ)償策略，可以同時(shí)顧及組間的數(shù)據(jù)量均衡；通過(guò)離群值的調(diào)整，能夠有效降低組間空間重疊度。

3.2 基于空間分布模式變化檢測(cè)的批量插入

插入對(duì)象后，空間索引的均衡性可能被破壞，被插入的節(jié)點(diǎn)也可能上溢。簡(jiǎn)單的局部變化可能會(huì)帶來(lái)索引樹(shù)復(fù)雜的整體調(diào)整。本文通過(guò)空間分布的變化檢測(cè)來(lái)實(shí)現(xiàn)數(shù)據(jù)更新后索引樹(shù)的調(diào)整。當(dāng)增加數(shù)據(jù)批量插入樹(shù)節(jié)點(diǎn)后，通過(guò)分散性指數(shù)對(duì)分布式模式進(jìn)行檢查，如果分布模式?jīng)]有發(fā)生變化，則增加數(shù)據(jù)引起的僅是索引樹(shù)的數(shù)據(jù)量上的變化而不是結(jié)構(gòu)上的變化，若分布模式發(fā)生了變化，則增加數(shù)據(jù)引起的是索引樹(shù)的結(jié)構(gòu)的變化，需進(jìn)行數(shù)據(jù)節(jié)點(diǎn)迭代調(diào)整。完整的插入流程如圖3所示。

圖3 批量插入流程圖Fig.3 Flow chart of buck insertion

（1）設(shè)定批量插入操作中的對(duì)象個(gè)數(shù)參數(shù)k。

（2）插入對(duì)象前進(jìn)行根節(jié)點(diǎn)是否存在判斷。若根節(jié)點(diǎn)不存在，則直接將對(duì)象插入置入緩存。若根節(jié)點(diǎn)存在，則再對(duì)待插入對(duì)象進(jìn)行范圍判斷。若插入對(duì)象落入現(xiàn)有Pattern－tree索引節(jié)點(diǎn)范圍內(nèi)，則通過(guò)節(jié)點(diǎn)范圍判斷尋找到包含該對(duì)象的數(shù)據(jù)節(jié)點(diǎn)。若同時(shí)有多個(gè)數(shù)據(jù)節(jié)點(diǎn)包含該對(duì)象，則增加到對(duì)數(shù)據(jù)節(jié)點(diǎn)MBR影響最小的數(shù)據(jù)節(jié)點(diǎn)中。若有多個(gè)數(shù)據(jù)節(jié)點(diǎn)插入后MBR沒(méi)有變化，則插入到節(jié)點(diǎn)數(shù)據(jù)量較小的一個(gè)數(shù)據(jù)節(jié)點(diǎn)中。

（3）若待插入對(duì)象不在現(xiàn)有Pattern－tree索引節(jié)點(diǎn)范圍內(nèi)，則首先置入插入緩存。當(dāng)達(dá)到插入緩存容量上限時(shí)，采用3.1節(jié)中描述的方法，對(duì)緩存內(nèi)所有對(duì)象進(jìn)行空間劃分，區(qū)分正常值與異常值。對(duì)正常值構(gòu)建Pattern－tree數(shù)據(jù)節(jié)點(diǎn)，并將其插入初始 Pattern－tree中。若 Pattern－tree根節(jié)點(diǎn)不存在，則將新構(gòu)建的數(shù)據(jù)節(jié)點(diǎn)作為根節(jié)點(diǎn)的子節(jié)點(diǎn)。對(duì)異常值采用自上而下的方式插入數(shù)據(jù)節(jié)點(diǎn)中。

（4）當(dāng)完成k次插入操作后，對(duì)Pattern－tree數(shù)據(jù)節(jié)點(diǎn)范圍內(nèi)的所有對(duì)象進(jìn)行分散性指數(shù)計(jì)算，若分布模式?jīng)]有發(fā)生變化，則按照（2）中的插入規(guī)則插入對(duì)象，并進(jìn)行節(jié)點(diǎn)上溢檢查。若有節(jié)點(diǎn)溢出，則選擇子節(jié)點(diǎn)數(shù)最大的一個(gè)節(jié)點(diǎn)，按照3.1中所述的方法進(jìn)行二路劃分。若沒(méi)有則直接完成增量插入。

（5）若分散性指數(shù)表明Pattern－tree內(nèi)的對(duì)象分布模式發(fā)生了變化，則依據(jù)目標(biāo)函數(shù)進(jìn)行逐步迭代求解；若由聚集分布變化為隨機(jī)分布，則目標(biāo)函數(shù)為描述隨機(jī)分布水平的分散性指數(shù)；若由隨機(jī)分布轉(zhuǎn)變?yōu)榫奂植?，則目標(biāo)函數(shù)為描述聚集水平的E。

（6）迭代求解結(jié)束即完成批量插入。

4 試驗(yàn)驗(yàn)證

采用江蘇省境內(nèi)真實(shí)數(shù)據(jù)對(duì)本文提出的數(shù)據(jù)劃分、空間索引構(gòu)建和查詢方法進(jìn)行驗(yàn)證。圖4中數(shù)據(jù)集A是河流和山地分割下的居民點(diǎn)數(shù)據(jù)，包含1588個(gè)點(diǎn)對(duì)象。數(shù)據(jù)集B為超市、加油站等興趣點(diǎn)數(shù)據(jù)，包含619 276個(gè)點(diǎn)對(duì)象。數(shù)據(jù)集C為道路網(wǎng)數(shù)據(jù)，包含241 331個(gè)線對(duì)象。數(shù)據(jù)集A用來(lái)測(cè)試本文提出的空間劃分算法。數(shù)據(jù)集B、C用于測(cè)試Pattern－tree的構(gòu)建效率與窗口查詢效率。試驗(yàn)環(huán)境為：IBM Thinkpad T410s，Inter（R）core（TM）i5CPU，3GB 內(nèi)存，Windows 7操作系統(tǒng)。

4.1 空間分布模式檢測(cè)與數(shù)據(jù)劃分試驗(yàn)

本試驗(yàn)選取GBI、STLT來(lái)與本文方法對(duì)比。GBI方法中采用k－means方法來(lái)進(jìn)行數(shù)據(jù)劃分，STLT采用R樹(shù)方法來(lái)進(jìn)行數(shù)據(jù)劃分。試驗(yàn)中采用線性R樹(shù)分組算法來(lái)實(shí)現(xiàn)STLT。采用ArcGIS中Average Nearest Neighbor Distance點(diǎn)模式分析工具對(duì)數(shù)據(jù)集A分析，結(jié)果表明該數(shù)據(jù)呈聚集分布且顯著性水平為0.01。按照本文分布模式指標(biāo)，對(duì)包含一個(gè)以上點(diǎn)對(duì)象的Hilbert區(qū)塊進(jìn)行樣方統(tǒng)計(jì)分析。結(jié)果表明數(shù)據(jù)集A在受限區(qū)域內(nèi)顯著的呈隨機(jī)分布，可采用算法時(shí)間復(fù)雜度和空間復(fù)雜度都比R樹(shù)線性分組和k－means分組方法小的等差劃分方法來(lái)進(jìn)行數(shù)據(jù)劃分。將試驗(yàn)數(shù)據(jù)劃分為5組，用虛線表示每組的MBR。結(jié)果如圖5所示，（a）為GBI方法劃分結(jié)果，（b）為STLT方法劃分結(jié)果，（c）為本文方法初始劃分結(jié)果，（d）為離群值調(diào)整后的本文方法劃分結(jié)果。

圖4 試驗(yàn)數(shù)據(jù)Fig.4 Sample data sets

由圖5可知，k－means方法能夠取得較好的空間聚集性。但是組間空間重疊度較大。R樹(shù)方法雖然能夠取得較好的節(jié)點(diǎn)利用率，但是由于沒(méi)有顧及空間分布特征，組間空間重疊度較大。結(jié)果C中用圓圈標(biāo)識(shí)出來(lái)的對(duì)象即為本文3.1節(jié)描述的Hilbert離群值。離群值對(duì)空間劃分后的組間重疊度產(chǎn)生了較大影響。進(jìn)行離群值調(diào)整后的結(jié)果優(yōu)于GBI、STLT方法。

圖5 數(shù)據(jù)集A劃分結(jié)果Fig.5 Result of partitioning of the dataset A

4.2 索引構(gòu)建效率試驗(yàn)

本文選擇STLT、SCB、GBI 3種支持批量操作的空間索引與本文方法進(jìn)行對(duì)比。采用C＋＋語(yǔ)言實(shí)現(xiàn)4種索引結(jié)構(gòu)。采用磁盤文件作為外存，選擇4KB作為葉子節(jié)點(diǎn)容量上限。考慮到：①4種方法的算法原理不一致，步驟不能一一對(duì)應(yīng)，索引構(gòu)建算法和步驟均有較大差異；②算法實(shí)現(xiàn)過(guò)程中，代碼實(shí)現(xiàn)細(xì)節(jié)對(duì)測(cè)試結(jié)果也會(huì)產(chǎn)生影響。因此，本文不進(jìn)行單項(xiàng)技術(shù)指標(biāo)的定量比較，而是借鑒文獻(xiàn)［7—10］中的測(cè)試方法，將索引構(gòu)建和查詢過(guò)程中頁(yè)面I／O訪問(wèn)次數(shù)作為衡量空間索引構(gòu)建和查詢效率的指標(biāo)。4種方法均完整地統(tǒng)計(jì)數(shù)據(jù)劃分、索引構(gòu)建等環(huán)節(jié)。分別選取占總量20%、40%、60%、80%與100%的數(shù)據(jù)子集來(lái)構(gòu)建初始索引樹(shù)。批量插入的數(shù)據(jù)為100。離群值比例選擇為10%。數(shù)據(jù)集B、C的試驗(yàn)結(jié)果如圖6、圖7所示。由圖可知，不管是點(diǎn)數(shù)據(jù)還是線數(shù)據(jù)，Pattern－tree構(gòu)建效率均優(yōu)于其他3種空間索引。其主要原因是，STLT中小樹(shù)的構(gòu)建依然是OBO方式。GBI、SCB引入了聚類方法，以聚類作為操作對(duì)象，效率要優(yōu)于STLT方法。其中，SCB依據(jù)先驗(yàn)知識(shí)來(lái)進(jìn)行聚類，因此效率高于GBI方法。GBI、SCB方法直接采用聚類方法，與STLT、SCB、GBI相比，Pattern－tree增加了空間分布模式探測(cè)步驟。但是，僅涉及均值、方差等的計(jì)算。Pattern－tree中僅包含節(jié)點(diǎn)容量上限，避免了節(jié)點(diǎn)分裂過(guò)程中的下溢檢查，減少了節(jié)點(diǎn)的合并操作；Pattern－tree批量插入過(guò)程中通過(guò)空間分布模式變化檢測(cè)，可以有效減少索引樹(shù)的整體調(diào)整。因此，Pattern－tree具有較高的構(gòu)建效率。

圖6 數(shù)據(jù)集B的4種空間索引插入效率對(duì)比Fig.6 Comparison of insertion costs of four methods for real datasetsB

圖7 數(shù)據(jù)集C的4種空間索引插入效率對(duì)比Fig.7 Comparison of insertion costs of four methods for real datasets C

4.3 窗口查詢效率試驗(yàn)

定義整個(gè)數(shù)據(jù)集空間范圍的1／4、1／16、1／128三種大小的窗口查詢范圍。隨機(jī)產(chǎn)生查詢窗口的起始位置，每個(gè)窗口查詢執(zhí)行10次，取I／O訪問(wèn)次數(shù)平均值進(jìn)行效率對(duì)比。數(shù)據(jù)集A、B的試驗(yàn)結(jié)果如圖8、圖9所示。由圖可知，無(wú)論是點(diǎn)數(shù)據(jù)還是線數(shù)據(jù)，Pattern－tree查詢效率均優(yōu)于其他3種空間索引。其主要原因是：①Pattern－tree中采用 Hilbert曲線對(duì)實(shí)體進(jìn)行編碼，能夠保證一定的空間鄰近性，能夠保證空間上鄰近的地理要素在物理存儲(chǔ)上盡量連續(xù)，能夠有效避免頁(yè)面的跳躍讀取，減少頁(yè)面訪問(wèn)；②Pattern－tree分別設(shè)置索引節(jié)點(diǎn)容量和數(shù)據(jù)節(jié)點(diǎn)容量，可有效降低索引樹(shù)的高度，縮短數(shù)據(jù)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度；③Pattern－tree采用自上而下的方式插入離群值，有利于降低組間重疊度，減少多路徑搜索。

圖8 數(shù)據(jù)集B的4種空間索引查詢代價(jià)對(duì)比Fig.8 Comparison of query costs of four methods for real datasetsB

圖9 數(shù)據(jù)集C的4種空間索引查詢代價(jià)對(duì)比Fig.9 Comparison of query costs of four methods for real datasets C

5 結(jié) 論

本文認(rèn)為支持批量操作的索引構(gòu)建難點(diǎn)在于批量操作的基本粒度的定義以及局部更新操作對(duì)索引樹(shù)的整體影響。本文以空間分布模式作為索引樹(shù)構(gòu)建的切入點(diǎn)，針對(duì)問(wèn)題一，在Hilbert空間填充曲線的基礎(chǔ)上引入空間分布模式分析方法，設(shè)計(jì)了一種兼顧空間聚集性、分組數(shù)據(jù)量等條件的空間劃分方法。該方法能夠保證空間上鄰近的地理實(shí)體在邏輯／物理存儲(chǔ)介質(zhì)上盡量連續(xù)，能夠有效避免空間查詢過(guò)程中的跳躍訪問(wèn)。該方法能夠兼顧空間聚集性、數(shù)據(jù)量、空間重疊度3種約束條件，能夠避免單純采用聚類方法所帶來(lái)的數(shù)據(jù)傾斜問(wèn)題，能夠避免單純采用空間索引方法所帶來(lái)的空間重疊問(wèn)題。索引構(gòu)建時(shí)，以劃分單元為單位，正常值采用自下而上，異常值采用自上而下，能夠同時(shí)顧及索引的構(gòu)建效率和索引的構(gòu)建質(zhì)量。針對(duì)問(wèn)題二，針對(duì)具體變化對(duì)整體的影響問(wèn)題，提出一種空間分布模式變化檢測(cè)的動(dòng)態(tài)更新方法，能夠有效避免索引的周期性重建。

文獻(xiàn)［11、20—21］等均在空間索引或者空間劃分中引入了Hilbert填充曲線。本文在Hilbert編碼反映空間鄰近性的基礎(chǔ)上進(jìn)一步進(jìn)行空間分布模式分析，對(duì)Hilbert編碼對(duì)象進(jìn)行多目標(biāo)空間劃分，將劃分單元作為批量操作的基本單位，取代OBO方式，實(shí)現(xiàn)了空間索引的快速構(gòu)建。本文還分析了Hilbert編碼在反映空間鄰近性時(shí)的異常值問(wèn)題，給出了異常值提取方法，設(shè)計(jì)了自上而下與自下而上相結(jié)合的構(gòu)建方法，能夠同時(shí)兼顧構(gòu)建與查詢效率。本文的后續(xù)工作還包括最優(yōu)的初始比例計(jì)算以及三維對(duì)象批量操作問(wèn)題。

［1］ WANG Yanmin，GUO Ming.A Combined 2Dand 3D Spatial Indexing of Very Large Point－cloud Data Sets［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：605－612.（王晏民，郭明.大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法［J］.測(cè)繪學(xué)報(bào)，2012，41（4）：605－612.）

［2］ AGHBARI Z A.CTraj：Efficient Indexing and Searching of Sequences Containing Multiple Moving Objects［J］.Journal of Intelligent Information Systems，2012，39（1）：1－28.

［3］ GARCIA Y，LOPEZ M，LEUTENEGGER S T.A Greedy Algorithm for Bulk Loading R－trees［C］∥Proceedings of the 6th ACM－GIS.Washington DC：［s.n.］，1998：163－164.

［4］ LEE T，LEE S.OMT：Overlap Minimizing Top－down Bulk Loading Algorithm for R－tree［C］∥Advanced Information Systems Engineering.Klagenfurt：［s.n.］，2003：69－72.

［5］ CHEN L，CHOUBEY R，RUNDENSTEINER E A.Merging R－Trees：Efficient Strategies for Local Bulk Insertion［J］.Geoinformatica，2002，6（1）：7－34.

［6］ CHOUBEY R，CHEN L，RUNDENSTEINER E A.GBI：A Generalized R－tree Bulk－insertion Strategy［C］∥Proceedings of SSD.Hong Kong：［s.n.］，1999：91－108.

［7］ LEE T，MOON B，LEE S.Bulk Insertion for R－tree by Seeded Clustering［C］∥Database and Expert Systems Applications.Prague：［s.n.］，2003：129－138.

［8］ GONG Jun，ZHU Qing，ZHANG Yeting，et al.An Efficient 3DR－tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249－255.（龔俊，朱慶，張葉廷，等.顧及多細(xì)節(jié)層次的三維R樹(shù)索引擴(kuò)展方法.測(cè)繪學(xué)報(bào)，2011，40（2）：249－255.）

［9］ BERCKEN J，SEEGER B，WIDMAYER P.A Generic Approach to Bulk Loading Multidimensional Index Structures［C］∥Proceedings of the 23rd VLDB.Athens：［s.n.］，1997：406－415.

［10］ ROUSSOPOULOS N，LEIFKER D.Direct Spatial Search on Pictorial Databases Using Packed R－trees［C］∥Proceedings of ACM SIG－MOD.Austin：［s.n.］，1985：17－31.

［11］ KAMEL I，F(xiàn)ALOUTSOS C.On Packing R－trees［C］∥Proceedings of CIKM.Washington DC：［s.n.］，1993：490－499.

［12］ CHEN L，CHOUBEY R，RUNDENSTEINER E A.Bulkinsertions into R－trees Using the Small－tree－large－tree Approach［C］∥Proceedings of ACM－GIS.Washington DC：［s.n.］，1998：161－162.

［13］ GAVRILA D M.R－tree Index Optimization［C］∥Proceedings of the Sixth International Symposium on Spatial Data Handling.Edinburgh：［s.n.］，1994：771－791.

［14］ SHEKHAR S，RAVADA S，KUMAR V.Declustering and Load－balancing Methods for Paralleling Geographic Information Systems ［J］. IEEE Transactions on Knowledge and Data Engineering，1998，10（4）：632－655.

［15］ MOON B，JAGADISH H V，F(xiàn)ALOUTSOS C.Analysis of the Clustering Properties of the Hilbert Space－filling Curve［J］.IEEE Transactions on Knowledge and Data Engineering，2001，13：124－141.

［16］ SAMET H.Hierarchical Representation of Collections of Small Rectangles［J］.ACM Computing Surveys，1998，20（4）：271－309.

［17］ GUTTMAN A.R－trees：a Dynamic Index Structure for Spatial Searching［C］∥Proceedings of ACM SIGMOD International Conference on Management of Data.Boston：［s.n.］，1984：47－57.

［18］ BENTLEY J L，F(xiàn)RIEDMAN J H.Data Structures for Range Searching［J］.ACM Computing Surveys，1979，11（4）：397－409.

［19］ WANG Yuanfei，HE Honglin.Spatial Data Analysis［M］.Beijing：Science Press，2007.（王遠(yuǎn)飛，何洪林.空間數(shù)據(jù)分析方法［M］.北京：科學(xué)出版社，2007.）

［20］ ZHOU Yan，ZHU Qing，ZHANG Yeting.A Spatial Data Partitioning Algorithm Based on Spatial Hierarchical Decomposition Method of Hilbert Space－filling Curve［J］.Geography and Geo－Information Science，2007，23（4）：13－17.（周燕，朱慶，張葉廷.基于Hilbert曲線層次分解的空間數(shù)據(jù)劃分方法［J］.地理與地理信息科學(xué)，2007，23（4）：13－17.）

［21］ LU Feng，ZHOU Chenghu.A GIS Spatial Indexing Approach Based on Hilbert Ordering Code［J］.Journal of Computer－Aided Design ＆Computer Graphics，2001，13（5）：424－429.（陸鋒，周成虎.一種基于Hilbert排列碼的GIS空間索引方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13（5）：424－429.）