面向集聚分布空間數據的混合式索引方法研究

周 侗,龍 毅,湯國安,胡雷地

(1.南通大學地理科學學院,江蘇南通 226007;2.南京師范大學虛擬地理環境教育部重點實驗室,江蘇南京 210046）

面向集聚分布空間數據的混合式索引方法研究

周 侗1,龍 毅2,湯國安2,胡雷地2

(1.南通大學地理科學學院,江蘇南通 226007;2.南京師范大學虛擬地理環境教育部重點實驗室,江蘇南京 210046）

空間數據索引技術可以有效地提高空間數據在存儲、處理、分析以及地圖可視化中的效率,其性能優劣直接影響GIS的整體性能。該文針對格網索引和四叉樹索引存在的問題,提出將四叉樹嵌入格網形成一種混合式空間索引結構,并分析其原理、數據結構與影響參數。理論分析及實驗證明,對于空間集聚分布狀態的海量地理數據而言,混合式索引方法以略高的存儲代價換取了更高的檢索、插入和刪除效率,是一種有效的空間索引方案。

混合索引;空間索引;GIS;地圖可視化

目前,GIS技術廣泛應用于空間相關的各領域,但也產生了一系列新問題,如數據量日益膨脹、空間分析過程復雜化等[1]。空間數據存儲與操作成為限制GIS發展的瓶頸問題之一,空間索引技術是一種常見的解決方案,其提供了一種快速、有選擇性地存取數據庫的機制,相當于一個映射機構,將屬性值轉換為相應記錄的地址或地址集[2]。GIS的空間分析與可視化過程,往往涉及多次重復耗時、復雜的幾何操作以及大量的磁盤存取過程,沒有一種合理空間數據索引方案的支持,必將直接影響系統運行的效率。前期實驗表明,空間索引方案和數據的空間分布類型具有一定的聯系,暫時沒有一種方案適用于所有類型的空間數據,對于集聚分布狀態的空間數據而言,使用已有的空間索引方案很難達到預期效果。本文總結了部分已有方案的特點,在此基礎上提出了基于格網和四叉樹的混合空間索引方案。

1 典型空間索引結構

1.1 格網索引

格網索引是規則地劃分二維數據空間,得到m ×n個矩形網格區域(圖1a）,每個網格區域為一個索引項,并分配一個動態存儲區,全部或部分落入該網格的空間對象的標識以及外接矩形存入該網格[3]。當用戶進行空間查詢等操作時,首先計算出擬查詢的空間對象所在的網格,然后在該網格中快速查詢所選空間對象。規則網格空間索引是一種分割空間對象的索引方法,其原理簡單、操作簡潔、可以直接訪問,在涉及的數據量不大、不需復雜的空間操作時,具有一定的適用性。但在建立索引前需要預知空間目標所覆蓋的范圍,可調節性相對較差。此外,網格劃分的精細程度取決于地理對象的大小、數量、分布及建庫人員的經驗,網格劃分過于粗略,每個網格內可能包含大量地理對象,搜索精度不高;網格劃分過細,雖然可以提高搜索精度,但一個對象會落入多個網格中,導致數據處理過程出現冗余現象。

圖1 集聚分布點群的格網索引與四叉樹索引Fig.1 Gridsand Quadtrees index structure of the aggregated point sets

1.2 四叉樹索引

四叉樹是建立在對區域循環分解原則上的一種層次數據結構,在計算機圖形學、圖像處理以及 GIS領域得到了廣泛應用,也適用于對空間數據的表示和索引[4-7]。如圖1b所示,它是一種面向空間地理對象的空間索引技術,將空間區域逐次劃分為4個等大的子區域,劃分的最大層次由用戶指定。四叉樹的每個節點有0個或4個子節點,每個子節點代表父節點的一個子區域。節點通常需要存放其所表示的空間區域范圍和屬于該節點的空間對象的標識(ID）。

四叉樹索引結構是一種清晰、容易建立的層次數據結構,其具有如下特點:1）通常使用順序存儲的線性表表示索引,內存需求量小,使空間查詢速度得到提升;2）插入和刪除操作簡便,平均耗時遠小于R樹。但由于其以空間劃分來組織索引結構的索引機制,當數據量較大時,四叉樹劃分的層數過少,將導致查詢性能的下降;劃分的層數過多,將導致存儲的冗余,從而增加空間開銷,影響查詢性能。

1.3 其他索引方法

常見的索引方法還有范圍索引、R樹、B樹、QR樹等,其原理不再贅述;部分學者嘗試將已有的索引方法相結合,取得一定的成效[8-12]。本文在對集聚分布數據的可視化實驗中,嘗試使用不同的空間索引方案,發現索引方法的效率受空間數據分布類型的影響,僅將一種空間索引方法應用于數據管理,有時難以大幅度提高系統運行效率。

2 空間數據的分布對索引的影響

2.1 空間數據分布的類型

地圖點群的空間分布通常分為均勻分布、隨機分布和集聚分布3種類型。均勻分布即點群在地圖每個區域的分布數量相同或相似,如社區內建筑物的分布;集聚分布主要是點群圍繞單核或多核呈簇狀分布,主要表現為點群集中分布于整個區域的個別區域,如本實驗所采用的南京地區企事業單位點群數據;隨機分布則介于均勻分布和集聚分布之間。

2.2 數據分布類型對索引方法效率的影響

均勻分布的地理數據,當采用格網索引時,數據均勻地分布于格網的每個單元中,因而格網索引的效率相對較高,基本不存在數據冗余,即包含地理對象數目較少的單元格不會大量出現;對于四叉樹索引類型而言,葉子單元中的對象數目上限設置較為合理,空間索引效率較高。因而,均勻分布的空間數據對于空間索引方法的依賴性較弱,只要索引方法應用合理,一般運行效率較高。

而對于集聚分布的點群,以單核的簇狀分布為例(多核的集聚分布點群情況與其類似）,當采用格網索引時(圖1a）,對集聚分布的點群進行m×n格網劃分,當m、n的值較小時,格網索引劃分的效果不明顯,沒有達到索引的目的;當m、n的值過大時,導致格網過多,但是集聚分布的點群仍分布在少數格網中,不僅降低了索引效率,而且造成了冗余。采用四叉樹索引時(圖1b）,當地理對象數量較多時,四叉樹所劃分的層數也較多,但隨著層數的增加,深度越大,四叉樹索引的效率就會降低。由此可見,此分布類型受空間索引方案的影響較為明顯,使用不當時很難提高系統運行效率。

隨機分布點群對于索引方法效率的影響介于均勻分布和集聚分布類型之間。基于以上分析,對于解決集聚分布的空間數據,四叉樹索引和格網索引方法均有不足之處,難以滿足效率和冗余度等方面的要求。而將四叉樹索引嵌入格網索引中,可以部分消除兩者的短板,形成一種新型的混合空間索引方案,一定程度上可提高操作效率,減少數據冗余,大大提高了數據查詢的性能。

3 混合索引方法

3.1 索引機制

3.1.1 原理 首先對研究區域中的地理對象進行格網劃分,檢查每個格網中地理對象的數量,如果其滿足閾值要求,說明已達索引目的,可結束索引;如果某些網格中地理對象的數量超過規定的閾值,需進一步對這些地理對象進行四叉樹劃分,直到四叉樹的葉子單元中的對象數量達到規定的閾值為止。如圖2所示,當地理對象密集地分布在若干個格網中時,仍需對其進行四叉樹劃分,直到每層中地理對象的數量達到規定的閾值為止。

圖2 混合索引示意Fig.2 Hybrid index structure for spatial data

3.1.2數據結構

(1）格網數據結構。網格編碼的整體存儲策略可將網格編碼的所有信息存入一個64位的長整型數中,計算時可直接使用位運算符提取行號、列號和Morton碼,效率較高。但由于標識位的存在,提取Morton的效率會有所降低。因此,可采用有冗余的網格編碼整體存儲策略,即將網格Morton的級數直接存儲在該編碼中,使得能夠直接根據級數判斷Morton碼的長度,而不需在計算過程中判斷標識位。

(2）四叉樹數據結構。四叉樹索引具體的實現方法為規定一個閾值,如果當前象限中的地理數據數目超過規定閾值,則需進一步劃分,否則結束索引過程。定義的四叉樹結構體如下:

這里,定義4個葉子節點分別指向4個子區域,i _num為某節點所包含的點數。

3.2 影響參數

3.2.1 格網索引的分塊數 格網索引的分塊數m、n決定了格網劃分的精細程度,因此也就成為選擇四叉樹索引的重要影響因素。在空間地理對象非均勻分布的前提下,若m、n的值較小,格網的數量較少,此時需對分布較密的地理對象建立四叉樹索引;若m、n的值相對較大,說明格網的劃分較精細,基本上每個格網中包括的地理對象都在規定的閾值范圍內,不需再進行四叉樹劃分。

3.2.2 四叉樹節點的閾值 當對地理對象進行格網劃分時,需要設定閾值以確定劃分的最小單元。由于閾值的大小對于空間索引的效率會產生一定的影響,因此閾值的確定要根據實際地理對象的分布而定。在格網索引中,閾值的大小一般是指網格的數量m、n,此參數會影響混合索引的實現。在四叉樹索引中,閾值是指當地理對象的數目達到該值時四叉樹不再細分,因而此參數直接決定了四叉樹的層數:閾值過大,層數相對較少,空間劃分不徹底;閾值過小,層數相對較多,增加了四叉樹的深度,造成數據冗余,會降低空間索引的效率。

4 實驗結果及驗證

為了進一步驗證各種空間索引方式在地理信息系統中的作用,本文以地圖可視化為例進行實驗。

4.1 地圖可視化實驗

4.1.1 實驗平臺 實驗采用神達掌上電腦 P350, CPU為400 M Hz,內存為256 M。實驗平臺為M icrosoft Visual Studio2005,開發語言為 C?。由于移動設計在硬件水平上存在著瓶頸,當處理的地理數據量達到一定程度時,效率明顯降低,并且存在存儲空間有限等不足,致使海量地圖數據的可視化受到一定的限制。通過多組實驗證明,基于此種硬件條件,當地理對象的數目超過2萬時,數據的顯示更新速度會明顯下降,因而考慮應對地理數據建立空間索引方案。本文基于移動設備,采用南京市全區的地理數據進行多組地圖可視化實驗。

4.1.2 實驗數據 采用南京市的1∶2萬地圖數據,地域范圍覆蓋了玄武區、鼓樓區、建鄴區、白下區、秦淮區、下關區、雨花臺區、浦口區、棲霞區、江寧區、六合區、溧水縣、高淳縣13個區(縣）等,主要包括點、線、面3種數據類型(點數據包括景點、企事業單位、賓館、酒店等,線狀地物包括道路、河流、城墻、行政界線等,面狀地物包括街區、綠地、湖泊等）;3類地物數量共為43 551,從整個地域范圍上看,數據呈典型的多核集中分布狀態,集中在南京的城區及縣(區）的城鎮中心周圍(圖3）。實驗分為3組,分別采用格網索引、四叉樹索引及混合索引結構,并對南京全區的地理數據建立混合空間索引方式(圖4）。

圖4 南京地圖數據的混合空間索引方式Fig.4 The hybrid index structure for spatial data of Nanjing

圖3 實驗數據示意Fig.3Experimental data

4.2 實驗結果驗證

本文空間索引的地圖可視化測試運行速度采用監測系統時間的方法確定。但是執行同類操作(如放大、漫游等）,由于地圖數據在屏幕區域上顯示的范圍不同,因而每步操作處理的空間數據量不固定,系統運行時間也不同。本文采用相對定性的方法表示每種空間索引方法的運行效率,用多組實驗的平均時間作為各種方法的評價標準,實驗結果如表1所示。可以看出,采用混合空間索引機制相比單一的空間索引方式具有明顯優勢。

表1 南京地圖數據的地圖操作效率Table 1 Efficiency comparison of different index structures used in the spatial data of Nanjing

5 結語

本研究構建了基于四叉樹索引和格網索引的混合索引結構,并通過基于移動設備的南京市全區地理數據可視化實驗,證明混合索引結構對于集聚分布的地理數據而言,較單純的四叉樹索引和格網索引具有明顯優勢,其以略高的存儲代價換取了更高的檢索、插入和刪除效率,特別是可以大大提升海量數據的索引性能。但本文僅提出了混合索引的構建方法及在集聚空間數據可視化中的應用,探討了幾個控制參數的地理含義,還需進一步研究其機理,以便應用于不同類型的空間數據中,提高空間數據分析及顯示效率。

[1] 陳菲,秦小麟.空間索引的研究[J].計算機科學,2001,28:59-62.

[2] 黃杏元,馬勁松.地理信息系統概論(第三版）[M].北京:高等教育出版社,2008.136-138.

[3] 張麗芬,王曉華,胡景松,等.基于網格劃分的幾種空間索引[J].北京理工大學學報,2004,24(2）:140-144.

[4] GAEGAN M.A efficient use of Quadtrees in a geographical info rmation system[J].Int.J.GIS,1989,3(3）:32-43.

[5] 董鵬,李津平,白予琦,等.基于改進四叉樹索引的矢量地圖疊加分析算法[J].計算機輔助設計與圖形學學報,2004,16(4）: 530-534.

[6] 董鵬,楊崇俊,芮小平,等.一種基于改進四叉樹的 GIS空間選擇查詢算法——以ESRISHAPE格式文件為例[J].計算機工程與應用,2003(13）:58-61.

[7] 袁達.一種新的線性四叉樹編碼的研究[J].測繪科學,1990 (4）:1-4.

[8] 徐少平,王命延,王煒立.一種基于R樹和四叉樹的移動對象空間數據庫混合索引結構[J].計算機與數字工程,2005,34:54-57.

[9] 黃明,陳哲.基于改進QR-樹的空間數據索引的研究[J].黑龍江工程學院學報(自然科學版）,2005,9(3）:18-20.

[10] 吳敏君,郭永洪,陳天滋.一種有效的混合空間索引機制[J].計算機工程與應用,2006,29:193-197.

[11] 吳煥萍,潘懋,胡金星,等.基于空間索引的規則格網DTM內插算法研究[J].地理與地理信息科學,2004,20(1）:43-46.

[12] 何小苑,閔華清.基于聚類的 Hilbert R-樹空間索引算法[J].計算機工程,2009,35(9）:40-42.

Research on the Hybrid Index Structure for Aggregated Spatial Data

ZHOU Tong1,LONG Yi2,TANG Guo-an2,HU Lei-di2
(1.School of Geographic Science,Nantong University,N antong226007;2.Key Laboratory of Virtual Geographical Environment,M inistry of Education,N anjing N ormal University,N anjing210046,China）

Studies on spatial data distribution and index structure have found that neither grid nor quadtree index structure is efficient fo r managing the aggregated spatial data.In case of the grid index structure,either the majo rity of the data is located in very few grids o r too detailed carving-up w ill lead to many grids,thus resulting in data redundancy.The only emp loyment of quadtree index structure is also unsatisfacto ry since data concentration w ill lead to the quadtree dep th increase,thus undermining index efficiency.Based on the advantagesof the aforementioned two structures,a spatial hybrid index structure is p roposed in this paper,w hich adop ts the grid index structure for the larger scale and then comp lements it by inserting quadtree index structure into it per parameters requirement.After a p reliminary analysis of its efficiency,details are given about how to construct such a hybrid index structure and to control its parameters.Within the experiment of this paper,the grid index structure adop ts a coding strategy w ith redundant data,w ith linear top-dow n quadtree index structure inserted.The two main parameters of the hybrid index structure are the resolution and the quadtree threshold respectively,w ith the former determining the number of quadtrees and the latter meaning the threshold num ber of geographical objects in a quadrant,w hen the quadtree w ill stop carving up.Both the grid resolution and the quadtree threshold shall be set in line w ith the distributing feature of geographical spatial data.The hybrid index structure is app lied to visualizing the spatial data of Nanjing City obtained from portable navigating devices.The research result show s that the hybrid index structure enjoysobvious efficiency superio rity over singular ones. Then it is concludes w ith recommendations fo r further study on inner mechanism of the hybrid structure,so as to enhance its stability and sp read its app lication.

hybrid index structure;spatial index structure;GIS;map visualization

P208

A

1672-0504(2010）01-0007-04

2009-08-18;

2009-10-23

國家863計劃項目(2007AA 12Z218）;國家自然科學基金(40571120）;南通大學自然基金(07z114）

周侗(1978-）,男,碩士,講師,從事GIS原理與制圖綜合方面的研究。E-mail:zhoutong@ntu.edu.cn