一種空間分布模式驅(qū)動的空間索引

吳明光

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 試驗驗證

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

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

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

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

由圖5可知，k－means方法能夠取得較好的空間聚集性。但是組間空間重疊度較大。R樹方法雖然能夠取得較好的節(jié)點利用率，但是由于沒有顧及空間分布特征，組間空間重疊度較大。結(jié)果C中用圓圈標(biāo)識出來的對象即為本文3.1節(jié)描述的Hilbert離群值。離群值對空間劃分后的組間重疊度產(chǎ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)建效率試驗

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

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

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

4.3 窗口查詢效率試驗

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

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

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

5 結(jié) 論

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

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

［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ī)模點云數(shù)據(jù)的二維與三維混合索引方法［J］.測繪學(xué)報，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樹索引擴展方法.測繪學(xué)報，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］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2001，13（5）：424－429.）