面向集聚分布空间数据的混合式索引方法研究

周 侗,龙 毅,汤国安,胡雷地

(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