索引空间（共5篇）
索引空间 篇1
近几年, 人们对地理资源、地球环境以及地理信息进行研究时产生了大量的空间数据, 地理信息系统又是以数字形式来表达现实世界的, 因此空间数据库成为地理信息系统的一个重要组成部分和核心技术。而空间索引技术则是空间数据库和GIS的一项关键技术, 空间索引方法的采纳与否以及空间索引性能的优劣直接影响地图数据库和地理信息系统的整体性能, 因此, 空间数据库索引技术的发展在空间查询乃至在整个空间数据的建设中, 都具有十分重要的意义。
1 什么是空间数据库索引技术
1.1 空间数据
在地理信息系统中, 除存放属性数据等非空间数据之外, 更多的用于存储譬如机器零件位置、国家或城市的地理位置等信息的空间数据。空间数据是一种带有空间坐标的多维数据, 包括文字、数字、图形、影像、声音等多种方式。空间数据是对现实世界中空间特征和过程的抽象表达, 用来描述现实世界的目标, 记录地理空间对象的位置、拓扑关系、几何特征和时间特征。位置特征和拓扑特征是空间数据特有的特征, 此外, 空间数据还具有定位、定性、时间、空间关系等特性。
1.2 空间数据库
1.2.1 空间数据库的概念
空间数据库指的是地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和, 一般是以一系列特定结构的文件的形式组织在存储介质之上的。由于传统的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷, 从而形成了空间数据库这一数据库研究领域。而传统数据库系统只针对简单对象, 无法有效的支持复杂对象 (如图形、图像) 。
1.2.2 空间数据库的特点
a.数据量庞大。空间数据库面向的是地学及其相关对象, 而在客观世界中它们所涉及的往往都是地球表面信息、地质信息、大气信息等及其复杂的现象和信息, 所以描述这些信息的数据容量很大, 容量通常达到GB级。
b.具有高可访问性。空间信息系统要求具有强大的信息检索和分析能力, 这是建立在空间数据库基础上的, 需要高效访问大量数据。
c.空间数据模型复杂。空间数据库存储的不是单一性质的数据, 而是涵盖了几乎所有与地理相关的数据类型, 这些数据类型主要可以分为三类:a.属性数据:与通用数据库基本一致, 主要用来描述地学现象的各种属性, 一般包括数字、文本、日期类型。b.图形图像数据:与通用数据库不同, 空间数据库系统中大量的数据借助于图形图像来描述。c.空间关系数据:存储拓扑关系的数据, 通常与图形数据是合二为一的。
1.3 空间索引
空间索引是指在存储空间数据时依据空间对象的位置和形状或空间对象之间的某种空间关系, 按一定顺序排列的一种数据结构, 其中包含空间对象的概要信息, 如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构, 空间索引介于空间操作算法和空间对象之间, 它通过筛选作用, 大量与特定空间操作无关的空间对象被排除, 从而提高空间操作的效率。
1.4 空间索引技术
空间索引技术, 就是通过更加有效的组织方式, 抽取与空间定位相关的信息组成对原空间数据的索引, 以较小的数据量管理大量数据的查询, 从而提高空间查询的效率和空间定位的准确性。由于空间数据自身的复杂性, 要查询一个空间对象, 整个过程的成本开销要比一般关系型数据库大得多, 特别是空间谓词求值的开销远比数值或者字符串的比较要大, 因此空间索引技术作为一种有效的数据检索手段, 降低了运算的成本和开销等诸多代价的付出。
2 空间数据库索引技术的概述
传统的数据库索引技术有B树、B+树、二叉树、ISAM索引、哈希索引等, 这些技术都是针对一维属性数据的主关键字索引而设计的, 不能对空间数据进行有效的索引, 因而不能直接应用于空间数据库的索引。因此, 设计高效的针对空间目标位置信息的索引结构与检索算法, 成为提高空间数据库性能的关键所在。
空间索引的研究始于20世纪70年代中期, 早于空间数据库的研究, 其初始目的是为了提高多属性查询效率, 主要研究检索多维空间点的索引, 后来逐渐扩展到其他空间对象的检索。空间索引性能的优越直接影响空间数据库和地理信息系统的整体性能。
目前存在的空间数据索引技术超过50种, 可概括为树结构、线性映射和多维空间区域变换三种类型, 从应用范围上可分为:
2.1 静态索引
静态索引包括以位置码为key值的一般顺序文件索引、粗网格线性四叉树索引、基于行排列码三级划分的桶索引等。
2.2 动态索引
动态索引包括适合内存索引的点四叉树、KD树、MX-CIF四叉树、CELL树、F树, 适合磁盘空间索引的基于Morton码的B+树、KDB树、B-D树、R树、MOF树、变形粗网格索引等。
这些方法绝大多数是从B树、哈希表、KD树改进而来的, 性能上只有细微的差别, 而且没有一种方法能够证明自己处于绝对的优势。由于在实际的应用中, 简单与稳定性是商业产品实现选择的首要因素, 所以在商用的DBMS中应用最为广泛的是R树索引, 这是因为R树相对简单, 能同时处理点和区域数据, 而且它的性能至少比那些更复杂的索引结构不差。同时, R树还有许多变形, 包括Cell树、Hilbert R树、Packed R树、R*树、R+树、TV树和X树等。
3 空间数据库索引技术的发展
基于传统技术改进优化而成的典型的空间索引技术包括R树索引、点四叉树索引、KD树索引、网格索引 (Boston, 1984) 等, 这些索引中很多也是基于空间实体的最小外包矩形建立的, 这些方法在点、线、面目标索引中各有其应用特点, 例如:R树能索引一定范围内的对象, 但是随着索引数据量的增加, 包围矩形的重叠会增加, 将严重影响查找性能;点四叉树的点查找性能较高, 但区域查找性能较差;KD树继承了二叉查找树在点匹配查找方面的优点, 但是其删除操作较复杂;网格索引查找简单, 查找效率较高, 适用于点目标的索引。
当今较为热门的索引技术是基于R树的空间索引结构, 但由于R树的基于MBR的索引机制, 对于精确匹配查询, 不能保证唯一的搜索路径, 从而造成多路径查询问题, 尽管R+树对此进行了改进, 但是R+树又带来了其他问题, 如随着树的高度增加, 域查询性能降低等。同时, R树家族对于大型空间数据库, 特别是多维空间数据的索引问题没有得到很好的解决, 易造成“维数危机”问题。现有的索引技术用于索引海量空间数据时, 往往由于存储空间开销的剧增或索引空间重叠的剧增, 而导致索引性能的下降。因此采用鲁棒的、维数及空间数据量可扩展的索引技术成为一种趋势。
1984年Guttman发表了《R树:一种空间查询的动态索引结构》一文, 由此揭开了动态索引的序幕, 其后, 人们在此基础上针对不同空间运算提出了不同改进, 形成了一个繁荣的索引树族, 这就是目前流行的空间索引技术。针对空间索引技术的研究, 各国研究人员投入了相当多的力量。著名的商业数据库厂商在支持地图数据时也都采用了空间索引的方法, 如Oracle 8i和Small World GIS中采用的四叉树索引技术, 以及Oracle 9i和Informix数据库中的R树索引技术。
空间数据库索引技术是在遥感技术、GIS、计算机技术、通讯技术等的发展前提下不断走向成熟的, 并且已广泛应用于如矿产勘查、资产清查、土地利用、城市规划、环境管理、航空航天、交通、旅游、军事、医疗等各行各业, 未来前景一片光明。
参考文献
[1]吴信才.空间数据库[M].北京:科学出版社, 2009.
[2]郭菁, 周洞汝, 郭薇, 胡志勇.空间数据库索引技术的研究[J].计算机应用研究, 2003.
[3]郭龙江, 李建中.空间数据库的索引技术[J].黑龙江大学自然科学学报, 2005, 6.
矢量图层空间索引的设计与实现 篇2
关键词：矢量数据,空间索引,四叉树,网络
在当今信息科技如此发达的社会, 地理信息系统获得前所未有发展。地理信息系统所面临的是组织、索引空间数据的问题。空间索引网络在分布式P2P环境下构建过程中, 将分布式QUAD-TREE与P2P CHORD网络相结合, 这样可同时对高效率的检索与良好负载平衡性能加以利用, 将网络索引更有效、更快捷地实现。
一、构建矢量数据结构索引网络
1、索引网络体系结构
体系结构由QUAD-TREE与CHORD两部分构成。下层将四叉索引树各层之间用控制点联系起来, 数据块最小外包矩形中心点则为控制点, 因每个四叉树节点都具有不同的地理区域范围, 所以, 为了确保索引的唯一性, 不会重复使用四叉树各个节点所对应的控制点。上层为CHORD网络, PEER节点是网络上的节点, 汇聚节点是CHORD上的节点。该层的通信层协议采用CHORD, 其为带弦环拓扑结构, 其路由定位机制具有高效、简单、可扩展、负载均衡等特点。
2、多图层、多尺度索引网络体系结构
以多尺度、多图层为基础进行思考, 下层是混合结构索引网络影响查询效率的主要原因, 因此, 需要分析下层分布式QUAD-TREE。在地理信息系统中, 通常以最小外包矩形为基础构建了四叉索引树, 亦或是改进。假设有S个图层, 而在每个图层中又包含了N个尺度, 如果将四叉树构建与每个图层的每个尺度中, 这样四叉树就需要构建S×N棵。不断增加比例尺与图层数, 同时对网络承载能力提出了越来越高的要求。四叉树的构建采用金字塔融合多尺度实现。将S× (N-1) 棵四叉树的负担减少, 每个图层建构一颗四叉树即可, 也将对网络负载能力的标准降低了。构建多尺度QUAD-TREE, 同一图层不同尺度之间具有的相关性可用金字塔形式表示。同一范围内, 地理信息从塔顶至塔底尺度越来越小、数据量越来越大、地理信息越来越细。除了存储本区域地理范围, 四叉索引数上的节点还需要对各自主节点与子节点的索引信息进行存储。
二、四叉树、网格、B+树、R树的对比
1、R树
R树所有叶结点在同一层, 且允许重叠各子树的索引空间。查找始于整个索引空间, 即从树的根结点开始进行查找。无论是对空间取悦中所有与之相交的空间目标进行查找, 还是对包含该点空间目标进行查找, 都可能是多路查找。但是, 当增加索引数据量时, 都会增大索引空间的重叠以及R数的深度从根结点开始查找, 相应增加了对须要访问的结点数、分枝数进行的查找, 显著降低了查找性能。
2、四叉树
在查找、删除、插入算法效率来看, 四叉树较R树更优, 在一定范围内, 四叉树性能越好, 说明其深度越大。当增加索引目标数, 四叉树的性能就更加突显出来, 显著优于R树。主要选择深度合适, 可以提升更高查找性能, 提升空间利用率。四叉树整体越具优势, 说明索引目标数越多, 因此适用于大型空间数据库系统。
3、B+树
B+树能够进行的查找运算有两种, 随机查找, 从根结点开始;顺序查找, 始于最小关键字。B+树索引不论是否实现成功查找, 但从根至叶子结点是每次查找必经之路。因此, 在查找过程中, 给定值等于终端结点上关键值, 索引才会终止。
4、网格
网格空间索引的基本思想是按照不同层次, 将空间区域划分为网格, 其大小相等, 将动态存储区分配给每一个小网格, 在该小网格动态存储区内, 存入空间实体标识号。通过划分, 每个小网格都会对应一个位移的空间实体, 在第一层某个小网格中有零维空间实体, 复杂空间实体、二维空间实体、一维空间实体落在哪层、哪个网格中, 需根据其MBR进行确定。
三、查询空间矢量数据算法
经过P2PQUAD-TREE和CHORD网络, 查询空间矢量数据。各节点间接或直接的通信以及网络核心功能由CHORD承担, 其PEER定位通过关键字得以实现, 在网络初始化, 建立四叉索引树之前, 需要对合适的关键字进行选取。定义关键字数据结构如下:
c Keyk= (scale, center, layername) , 其中, layername是图层名;center为数据块控制点的坐标;c Keyk为空间矢量数据尺度。关键字可作为QUAD-TREE中索引的唯一标志, 每个矢量数据块在经过划分后, QUAD-TREE中的索引节点与KEY逐一对应。查询算法伪代码如下:
一个PEER向另一PEER发送消息由“→”表示。集中式与分布式系统报文处理能力的分析可采用数学方式, 在降低网络负担的同时, 通过数据分析能够提升索引效率。集中式系统是在网络环境相同的条件下, 在同一节点上完成查询与数据操作的系统。假设由P个汇聚节点构成了上层CHORD网络, 且网络中的网络稳定汇聚节点不会退出。图层有S个, 每个图层包含N个尺度, 数据最大划分层数为fmax (fmax≥fmin) , fmin为最小划分层数。因尺度一共有N个, 在得知fmax及fmin的前提下, 推算N=fmax-fmin+1。假设将X作为每个图层需要查询数据块的个数, 被查询的尺度是scale (1≤scale≤N) , 划分层数越小说明尺度越大, 数据的划分层数在第scale个尺度时为:lN=fmin+scale-1。1作为系统四叉查询过程中节点向下遍历的次数, 因此, 查询一颗四叉树X块数据需要的报文数是:W=X´ (lN-fmin+1) =X´scale, S个图层就有:WS=S´4fmin´W。针对集中式系统而言, 同一个节点上着数据, 因此, 所有的报文由该节点进行处理。分布式系统处理报文能力提高, 说明网络中增加了汇聚节点, 从而将分布式系统的优势体现出来。
四、总结
多用户并发所产生的问题在应用空间数据服务技术后得以解决, 文章介绍P2P空间矢量数据索引网络, 并因此为基础, 探讨了查询索引网络空间矢量数据算法。以索引网络为前提, 将该较为简单的索引网络进行改进, 这样能够将网络性能更进一步提高, 如将缓存机制引入等。
参考文献
[1]付仲良, 刘思远.MR-tree空间索引的Voronoi图改进及其并行空间查询方法[J].武汉大学学报:信息科学版, 2012 (12) .
[2]余冬梅.基于K-Means聚类的R-树空间索引方法研究与分析[J].科技导报, 2012 (11) .
索引空间 篇3
近年来, 空间数据信息在国内外各行业信息处理中的比重不断上升, 在众多的业务领域中得到广泛应用, 特别是与空间及地理分布数据密切相关的空间信息系统 (GIS) [1], 如城市规划/建设管理、物流管理/控制和网格计算等。
显然, 传统的数据库管理系统无法有效地管理空间数据信息, 因此, 处理和管理空间数据信息的空间数据库管理系统应运而生。目前发展起来的主流空间数据库管理系统通常采用基于中间件技术来管理和处理相关的空间数据信息, 其中间件技术是介于GIS和空间数据库载体之间的转换层, 它屏蔽了不同的操作系统平台和数据库平台的差异, 实现了空间数据管理和应用所需的技术的专业化, 使得各类前台终端实现高度的数据共享和功能互操作。该类中间件技术的杰出代表是空间数据库引擎, 空间数据库引擎基于传统的关系数据库对空间数据信息进行有效的处理/管理, 且提供特定的空间数据关系运算和空间数据分析功能。
对空间数据进行合理的组织和管理可以有效的提高空间数据处理/管理的效率, 显然, 空间数据库引擎中的空间数据库索引技术是提高空间数据处理/管理的效率的一个重要机制, 是空间数据库处理技术的重要组成部分。
目前业界流行的空间数据库索引技术中, 有源于B树的R-树索引[2], R-树索引的两种变体分别是R*-树索引[3]和R+ -树索引[4];还有基于对空间递归分解的层次型四叉树索引[5]等等。其中, R*-树的索引技术是最成熟, 也得到了广泛的实际运用。但是传统的R-系列索引技术允许空间数据索引码互相覆盖, 从而导致了空间索引路径的不唯一, 降低了空间数据项的查询效率。在此, 基于R*-树索引方法, 结合具有严格空间组织性的四叉树精髓, 文中完成了对R*-树的构造算法的改进, 尝试性地提出一种新的混和索引技术——R*Q-树索引。
1 经典的R树和R*-树
1.1 R-树
1984年由美国Guttman教授首创的R-树[2]空间索引结构是一个高度平衡的数据结构, 它基于对经典的B+树索引结构的改进与扩展, 以有效地处理空间数据信息。R-树的每个结点包含一个矩形区域的索引码, 该矩形区域由对应结点的所有子结点的最小外包矩形嵌套组成, 其中所有的最小外包矩形的每一条边都和一个全局坐标系的坐标轴平行。同时, R-树的树状结构具有以下特征, 即:
· 若根结点不是叶子结点, 则它至少有两棵子树;
· 除根之外的所有中间结点 (乃至叶子结点) 均至少有m个子结点, 至多有M个子结点;
· 所有的叶子结点都要出现在同一层 (体现了R-树的高度平衡) 。
由于一个给定结点的两个子结点的边框允许重叠, 因此构造一棵高效的R-树的成败取决以下两个重要的性能指标:覆盖因子和交叠因子。覆盖因子过大会使得R-树的索引降低;交叠因子无序又会使得基于R-树索引路径不唯一。其中, 覆盖因子度量了R-树所覆盖的空白区域, 即间接衡量了相应的静态空间对象的覆盖程度。交叠因子度量了同一层水平结构上存在的多个结点的索引码的叠加程度。理想情况下, 应力求所构造R-树的覆盖因子和交叠因子均达到最小化。针对如何使R-树的交叠因子最小化的问题, 提出了一种有效地改进R-树索引方法的设想, 其设计与实现形成R*-树索引方法。
1.2 R*-树
R*-树的树状结构与R-树类同, 且其基于R*-树的索引方法在对R*-树的构造算法、结点插入算法、结点删除算法和结点检索算法上都与R-树索引方法中的相关算法基本相同。它们的主要区别在于为了最小化树状结构的交叠因子, 考虑在R*-树的构造算法和结点插入算法中融合有效的插入路径选择机制、结点有效分裂机制和强制重新插入策略。其中:
· 插入路径选择机制 在选择插入路径的时候, R*-树除了考虑面积因素外, 还考虑了矩形索引码的重叠因素。该选择机制的基本思想可归结为:
从根结点开始选择插入路径, 如果当前结点的子结点指向中间结点, 那么选择包含插入矩形后其矩形重叠面积增长最小的矩形索引项;若存在矩形重叠面积增长相同的多个矩形索引项, 则选择矩形面积增长最小的矩形索引项;若存在矩形面积增长相同的多个矩形索引项, 则选择矩形面积最小的矩形索引项;
如果当前子结点指向叶子结点, 那么选择包含插入矩形后, 其面积增长最小的矩形索引项;若存在面积增长相同的多个叶子结点, 则选择其矩形面积最小的结点索引项。
· 结点有效分裂机制 针对某多维空间矩形, 设 (lxi, hxi) 为该矩形在i维的映射。对于每一维, 将等待分裂的M+1个矩形索引码分别以lxi和hxi的值排序, 由此产生针对特定维度下的两组有序的矩形索引码, 然后确定M-2m+2种将M+1项划分为两组 (其中每组的元素个数介于m与M) 的分类方法。分类为:每一组分别取这一排序中的前m项乃至最多为M-m+1项, 另外一组取余下的M-m+1乃至最少为m项。
接着, 针对取得的每组分类结果, 采用确定的量化公式[6] (基于对矩形索引码面积、边长和相应重叠度) , 计算其相应的有效权值, 最终依据权值大小确定最终有效的分裂方法。
· 强制重新插入策略 R*-树的构造颇具动态性, 即对于相同的空间数据集合, 若空间数据项插入的次序不同, 则可构造出结构迥异的R*-树, 从而严重影响对其索引的效率和性能。诚然, R*-树的构造算法中引入了小空间范围内的动态重组机制, 然而, 为了确保在全局范围内, 避免R*-树中间层索引码的重叠度过大, 在相应的R*-树的结点插入算法和结点删除算法中均采用了有效的强制重新插入策略[6]。
2 R*Q-树
大多数的空间数据项的插入过程中若采用了上述R*树的索引方法, 均能够使得所构造的空间数据项树状结构处于一个相对稳定和平衡的状态。然而, 若碰到诸如所处理的空间数据项其形状差异较大, 或者相邻的空间数据项距离过远等情形, 则R*树的索引方法的性能就会大大下降。
在此, 针对R*-树索引方法存在的缺陷, 即当一组空间数据项尚未达到分裂的需求, 且相互之间的形状和相对的邻接距离差异较大时, 就会造成R*-树索引结构的中间结点索引码的覆盖度增大, 其空间索引码的交叠因子也增大, 乃至基于R*-树索引技术的结点分裂次数增多, 最终导致R*-树索引效率大大降低。本文提出了一种基于R*-树索引方法的R*Q-树索引改进算法。
R*Q-树索引改进算法在原有R*-树索引方法的基础上融合了传统的四叉树[6]的索引思想 (四叉树建立于对区域循环分解的基础上, 是一种结构清晰的层次型的索引技术, 因而具有聚集空间目标的能力[6]) 。即引入适当的动态指导机制后, 在插入空间数据项的同时, 考虑对整体空间对象进行嵌套式的四叉分解, 直至能够包含该层矩形索引码的最小粒度为止。而文中所提出的适当的动态指导机制是指针对该最小粒度的空间对象, 先判断插入的空间数据项和该层的矩形索引码之间是否位于不同的四分象限。若两者位于不同的四分象限, 则可以适时地为插入的空间数据项创建预处理结点;若两者位于相同的四分象限, 则进一步对该层的矩形索引码进行嵌套式的四叉分解。然后针对所处理的空间对象, 若插入的空间数据项和其兄弟节点位于不同的四分象限, 则为其建立预处理结点;否则按照R*-树原有的插入算法完成空间数据项的插入过程。
为了配合上述结点插入算法的改进, 文中还有效地将四叉树的索引思想引入到R*-树的结点分裂算法, 在此称之为R*Q结点分裂算法。即在结点需分裂时, 首先对整体空间对象进行嵌套式的四叉分解, 直至能够容纳分裂结点的父结点矩形索引码的最小粒度为止。然后针对最小粒度的空间对象, 若被分裂结点和其兄弟结点位于不同的四分象限中, 则保持该分裂结点矩形索引码不变, 且在该分裂结点上加深一层, 将被分裂结点分裂成两个结点处于新层。
2.1 R*Q-树插入算法
在此算法中, 引入四叉树分解的基本思想, 提出了“最小包含的标准四分格”的设想。即假设索引的总体空间为X, 将X按照标准的四分格[6]的划分方法划分。能够包含插入空间数据项的最小标准四分格就称为空间数据项的最小标准四分格 (文中称之为MSQ) 。
R*Q-树结点插入算法在插入空间数据项之前, 先调用NeedIndependence算法来判断是否需要创建一个独立的新结点来存储它, 否则就调用R*-树的原始插入算法。在插入的过程中如果结点需要分裂, 就调用R*Q-树结点分裂算法。
具体地, R*Q-树的插入主算法如下所示:
Algorithm R*Q-树插入主算法
输入:
在插入主算法中调用了NeedIndependence算法来判断对插入的空间数据项是否创建预处理点。若插入空间数据项在它和当前层次的其他子结点索引目录矩形合并之后的MBR[1]中, 独立地属于不同的象限集合, 且满足相应的附加条件, 则创建一个独立的新预处理结点来存储插入的空间数据项。
该NeedIndependence算法的伪代码如下所示:
2.2 R*Q-树的分裂算法
当遇到某个结点的子结点个数超过最大值M时, 插入的空间数据项结点就需要被分裂。
具体地, R*Q-树的分裂算法如下所示:
3 R*Q-树的应用与展望
本文提出的R*Q-树索引改进算法完成了对经典的R*-树索引方法中原有的结点插入算法和结点分裂算法的有效改进, 该成果可以应用于R*Q-树索引方法的构造算法中。
在此采用随机的空间数据项插入样本 (空间数据项个数要求>20000) 比较了基于R*-树索引方法的构造算法与基于R*Q-树的索引结构构造的改进算法中空间数据索引码的交叠程度, 即当插入相同序列不同量级的空间数据项时, R*Q-树和R*-树构造的索引结构中的交叠因子交叠率。实验统计结果如图1所示, 当插入的空间数据项的量级为5000以下, 此时R*Q-树和R*-树和构造的索引结构的交叠因子交叠率近似相同, 此时, R*Q-树改进算法的功效不显著;然而, 随着插入空间数据项数量的递增, 特别是其数量级达到5000到15000之间时, R*Q-树改进算法的结点预处理机制所具有的聚集功能使得R*Q-树的交叠因子交叠率开始低于R*-树的交叠因子交叠率;特别是当其数量级达到15000以上时, R*Q-树的改进效果陡现, R*Q-树的交叠因子交叠率明显优于R*-树的交叠因子交叠率。
分析实验数据结果, 可以得出以下的结论:对于同样的拓扑结构, R*Q-树索引结构的结点总数比R*-树索引结构的结点总数多, 然而R*Q-树索引结构有效地减少了空间数据索引码的交叠因子交叠率。实验结果证明随着空间数据项的大量插入, 基于R*Q-树的索引结构其优势就会愈发明显, 达到了通过减少空间数据索引码的覆盖度和交叠度, 进而提高空间数据项索引效率的目标。
总之, R*Q-树索引结构的构造算法基于R*-树索引结构的构造算法, 融入了传统的四分树的精髓, 采用R*Q-树索引结构在空间数据项插入时, 采用了有效的动态指导机制, 即为符合条件的空间数据项创建预处理结点, 而不是单纯的将空间数据项按具有最优权值的那种组合插入。如此, R*Q-树索引结构在插入空间数据项时会牺牲一定的数据存储空间和空间利用率, 但是随着空间插入数据项的递增, 所采用的动态指导机制, 将会较好地改进原有R*-树索引结构的索引效率。文中主要完成了基于R*-树索引结构的构造算法的部分改进工作, 提出了基于R*Q-树索引结构的构造算法。然而, 在R*Q-树索引结构构造完成之后, 如何维护与调整其索引结构使之高效地运转, 乃至改进与之相适应的空间数据项查询算法和空间数据项删除算法的工作, 还有待于进一步地探讨。
参考文献
[1]Shashi Shekhar, Sanjay Chawla.空间数据库[M].谢昆青, 马修军, 杨冬青, 译.北京:机械工业出版社, 2004.
[2]Guttman A.R-trees:A Dynamic Index Structure for Spatial Searching.Proc.ACMSIGMOD[J].1984:47-57.
[3]Bechmann N, Kriegel HP, Schneider R, et al.The R*tree:An Eficient and Robust Access Method for Points and Rectangles.Proc.ACMS IG-MOD[C].Atlantic City, USA, 1990:322-331.
[4]Sellis T, Roussopoulos N, Faloutsos C.The R+-tree:A Dynamic Index for Multidimensional Objects.Proc.13th Int.Conf.on Very Large Da-tabases[C].Brighton, U.K., 1987:507-518.
[5]Finkeland R A, Bentley J L.Quadtrees:Adata structure for retrieval on Compositive keys.Acta Informatic, 1974, 4:1-9.
索引空间 篇4
目前的数据储存模型主要有两种: 按行存储和按列存储,位图索引多以按列存储形式存储。大多人认为位图索引常常用来处理基数相对较低的数据列,然而实际上,当运用于较高基数的列,位图索引的查询性能也可以有一定的提高,如果这时使用原始的简单位图索引可能是不合适,但是当运用范围编码和分段的策略时[1],就会有一个可观效果。位图索引数据库大多是按列存储的,以一列为存储单位,下文提及的HBase[2]便是一个按列存储的数据库,目前应用广泛。位图索引运用逻辑运算( 与、或等) 来快速实现查询。因位图索引中相同的数据较多,这就使得数据压缩具有可行性,常见的压缩算法有BBC[3]、WAH[4,5]、PLWAH[6]、EWAH[7]、CONCISE[8]、COMPAX[9,10]等等。
目前的海量数据使得如果仅运用某些技术策略处理数据的效果并不如人意,同时兼顾经济性,使得在提高处理速度的同时能够降低数据处理的成本, 云计算正 是因为以 上问题得 以广泛应 用。 Hadoop[11]是其中的一个平台,是目前最受欢迎和使用最为广泛的平台,使用的Mapreduce[12]分布式处理机制,目前也有的版本使用的是Yarn。其受欢迎的原因是具有很好的扩展性、容错性和通用性。Hadoop所采用的分布式文件系统HDFS[13],把数据分成块后进行存储,这种文件系统非常适合海量数据的处理。
本文主要运用Hadoop分布式平台处理大规模数据,文献[14,15]中表明其具有可行性,本文以位图索引为主体,提出BMIH策略。在Hadoop平台上建立位图索引,使用改进的压缩策略提高位图索引查询效率和降低占用空间,从而解决数据处理难题。
1位图索引及压缩编码的改进
位图索引的主要优点是对于产生数据量较少, 以bit为单位的,即为二进制形式,处理时只需运用或与非( or、and、not) 等的位运算即可,免去中间类型转换等处理。
位图索引的重复数据较多,产生冗余,对其压缩很有必要,处理后节省的存储空间是可观的。BBC、 WAH、COMPAX、PLWAH、EWAH等压缩编码方式可以直接参与查询运算。COMPAX可以实时的进行索引建立,从而减少内存的消耗,并且适合大规模线上处理和拥有较高压缩效率。COMPAX编码是使用的一种模板( codebook) ,其主要是压缩连续的0,首先是把一系列连续的bit位划分成31位的块 ( 取字长32位) ,下面就是COMPAX的四个模板:
( 1) [L]代表bit位上面是1和0的混合数据块,编码如下。
第一排为原始数据,第二排为编码后的数据。
( 2) [0F]代表一系列连续的0块,以下举例为32 × 31位0,前3位为类型编码,后29位是原始31位数据块的编码,数据量减少明显,编码如下:
( 3) [LFL]代表一个[L][0F][L]序列,当这两个L字中都只有一个字节为非0,同时0F不能超过256 × 31位( 因是8位bit最大能组成256 ) ,这样就可以把这个序列只用一个字就能存储了。一个具体例子见图2,另外[FLF]与[LFL]类似。
上面介绍了COMPAX的压缩编码方式,COMPAX编码主要考虑压缩数据中的大量连续的数字0,有设置了类似于WAH中的F型字的0-F型字, 但是并没有 考虑到连 续的数字1,这就使得COMPAX编码压缩率有被进一步提高的可能。当数据量较大的时候,尤其是使用Bit-sliced[16]编码方式或者在位图索引使用范围编码策略时,这其中的数字1的数量在整个位图数据中的比重将会大大增加,一定情况下甚至比数字0还要多,这就使得单纯使用COMPAX进行编码的会有不足之处。在COMPAX上增加了一个模板1-F型字,即对全是数字1的字也可以进行压缩。同时对于在位图中的0和1的个数相接近时的考虑并不多,在目前的云环境中, 基数不断增大,位图中的1和0有趋于接近的趋势, 因此在COMPAX的基础上进行进一步改进非常有必要。故可在L型字上进行进一步划分,这对压缩率将会有一定的提升。我们知道在COMPAX中, LFL型字中的L型字允许有一个字节是0和1的混合,但是定义了这个字的其余位都是0,我们把这类L型字记为0-L,由此可扩展一个L型字,允许一个字是0和1的混合,另外的三个字节都是1,并把这类L型字记为1-L,改进方法记为ACOMPAX( advance COMPAX) ,得到改进模型。
模板种类一共五种,分别如下。
注: 以下L型字节为多字节0和1混合字。
接下来介绍具体编码方式。
( 1) 对一个字中的四个字节分别记为第1、2、3、 4字节,以字节为单位,如果两个或者两个以上的字节中是0和1的混合( 如1、2或者1、3字节都是0和1的混合,剩余位都是0或者都是1) ,那么则记这个字为L型字,编码时把编码字的第1个字节的第1位置为1,如下所示。
( 2) 对于一个全是0的字,记为0-F。编码时第1个字节的第1位置为0,第2、3位为00代表0-F型字,例如56 × 31位0的编码方式如下:
对于一个全是1的字,记为1-F,第2、3位11代表1-F型字,例如: 56 × 31位1的编码如下:
对一个字中的1、2、3、4字节,如果只有一个字节中是0和1的混合( 如第1或者第3字节是0和1的混合) ,剩余位都是0,那么则记这个字为0L型字,例如0和1混合字在第四个字节中,编码如下:
对一个字中的1、2、3、4字节,如果只有一个字节中是0和1的混合,剩余位都是1,则记这个字为1-L型字,举例如下:
( 3) 对一个COMPAX中的[LFL]型字,由于扩展了L型字和F型字,就会有多种情况,表示为:
[0-L或1-L][0-F或1-F][0-L或1-L]。对于LFL型字,对于F型字的块数不超过64个,编码方式如下:
从编码字首位开始,字的第1位置为0,第2、3位为01,这样表示一个LFL型字,若第4位为0则表示第一个L型字为0-L,若第4位为1则表示1L; 第5位为0是表示F型字是0-F型,若第5位为1则表示1-F型; 第6位为0是代表第2个L型字是0-L型,若第6位为1则表示1-L型; 第7、8位表示第一个L型中的0和1的混合所在的字节,第9、10位表示第2个0-L或1-L型字中的0和1的混合所在的字节,则这个字中的第2个字节剩余的6位表F型字的个数,第3个字节表示第1个0-L或1-L型字中的0和1混合字节位置,第4个字节表示第2个0-L或1-L型字中的0和1混合字节。
( 4 ) 对于COMPAX中的[ FLF ]型字,表示为:
[ 0-F 或 1-F ][ 0-L 或 1-L ][ 0-F 或 1-F ] 。
对于F型字的块数不超过256个,编码如下:
第1位为0,第2、3位为10,这样表示一个FLF型字,若第4位为0则表示第一个F型字为0-F,若第4位为1则表示1-F; 第5为0是L型字是0-L,若第5位为1则表示1-L; 第6为0是代表为第2个F型字是0-F,若第6位为1则表示1-F; 第7、8位表示L型中的0和1的混合所在的字节,这个字中的第2个字节表示第1个F型的字节数,第3个字节表示L型字节中0和1混合字节,第4个字节表示第2个F型字节数。
下面将对改进后的COMPAX进行分析。使用ACOMPAX编码方式对数据进行编码,编码后形成数据流,数据流中的数字出现概率之间相互独立,假设对数据流出现0-F的概率为f0,出现1-F的概率为f1; 出现0-L的概率为: l0; 出现0-L的概率为: l1,那么多于一个的字节中是0和1混合的L型字的概率为: 1 - f0- f1- l0- l1。以上的数据的概率之间是相互独立。
假设在数据量极大,接近于无穷大,我们也假设三个字为一组并计算它的字长期望值,用字母E表示。
对于COMPAX,其中的LFL和FLF型字进行了压缩,可以得出LFL型的概率为:
而FLF型的概率为:
对于这两种情况,可以使用一个字就可以存储, 否则需要多于一个字去存储,由此可以得出COMPAX的长度期望值E2,其有关系:
分解此关系式得到:
最后是ACOMPAX的长度期 望值E2,同理可得:
LFL型的概率为:
而FLF型的概率为:
并得到关系:
从概率之和可以看出,P3+ P4≥ P1+ P2,在最坏的情况下是相等的。这时候来衡量改进后的COMPAX相对于COMPAX的效率上的提升效果:
分别取l0= l1= l和f0= f1= f化简后得到:
由此可以根据函数得出改进后的编码方式的改进效果,如图1所示。
2位图索引的建立与分析
本节研究的主要内容基于MapReduce的位图索引的构建方法,主要通过Map过程和Reduce过程实现。索引常常是建立在某些属性列之上,对于位图索引也是同样,因此本章位图索引的建立是通过扫描需要建立索引的数据列,依次按行的排列顺序依次从上往下读取特定列的属性值,并对读取的列属性值运用位图编码方式处理。整个过程主要分布在Map和Reduce两个函数内实现,Map函数主要负责单个数据块的位图索引建立,在Reduce函数中对Map函数的结果进行归并和进一步的处理,最后输出完整的索引数据。
考虑到一个数据表有n条记录,并且每一列有k个不同的值,那么某个特定列的位图索引大小为s = nk比特( bit) ,假设需要处理的数据类型为简单数据类型中的double型( 64位) ,那列属性源数据占用的也为s bit,这也就意味着,如果不对索引压缩的情况下,当k值达到64时,这个位图索引数据已经达到了源数据的大小了,与此同时实现算法时同样会把ROW ID以及其他特性添加到位图索引数据中,这时候的索引建立耗时和占用空间优势就减弱了,并且如果索引数据过大也同样会使得进行数据查找和检索时的效率有所降低。同时随着索引占用空间的变大,维护索引的成本也就相应的变大了,当然很多时候列的标识符类型占用空间是要比double型大的多。因考虑到位图索引适合属性基数较小的属性列的特性,兼顾空间和效率优势,所以选取当一个基数在64以下的时候就会对其建立位图索引处理,也就是说以64为界点。
接下来是在Hadoop中建立位图索引的算法过程设计,为了提升建立索引的速度,首先将要使用的数据集TPC - H上传至HDFS中,数据上传至HDFS过程中完成了数据分片的过程。对HDFS中的文件Hadoop可以直接读取,在建立索引的时,使用依次按列加载数据,同时读取行编号,并设置读取列结束标志,用来分割不同的列。假设有整个数据集S,其有n个记录,对应为R1,R2,…,Rn,任意Ri∈S,每条记录有m个属性,依次对应为T1,T2,…,Tn,每个属性对应有多个取值,把第i个属性的对应第j个记录值记为Tij,其属性的基数为k,对应的唯一值即属性值的取值记为: Ni1,Ni2,…,Nik,Tij与Nik的关系为对应集合关系:
a,b是介于1 ~ n的整数,即: a,b ∈ [1,n]且b ≥ a,用来表示第a,b个记录,c ≤ k且为整数,这是为表示ROW ID的需要。Bi取值为0或者1。 V[a]为位图向量的一个bit位,其代表第a条记录的bit位,初始状态全部位设为0,当使用位图索引时描述的原始的过程如Algorithm l和Algorithm 2。
Algorithm 1描述了Hadoop的Map过程,我们把算法命名为BMIH( Bitmap index on hadoop) ,首先是读取Ti列数据,统计属性列的基数,并依次编号, 这时候分别记录起始ROW ID和最后的ROW ID为d和e,然后以编号数据为序列开始循环读取数据, 如果在一列的数据中读到数据与已经编号的数据有相同,则设定相应位,如有: Ni1= x,同时在一列中第一数据就为x,那就把向量V的第1位即V11置为1, 如果第1位不是x,那么就不置值,而本该置为0的,因为在初始化向量时,把每一位都置为0了,并返回,读完整个数据块。依次类推,最后得某列的一个属性值和一个与之对应的位图向量组成( key,value) 形式键值对,即( Ti,Nij,Vi) 。
Algorithm 2描述了Hadoop的Recuce过程。首先是初始化一个值全部为0的向量,然后用这个向量将key( 键值) 为Nij的向量运用或操作,这样便得到了完整的key为Nij以及对应的向量值,最后输出这个完整的键值对。再后就是是多个这样的键值对也就形成了一张逻辑上的表,这张表就是索引所需要的。表的横轴为属性各个值,纵坐标为Row ID, 上述算法过程类似于把这一张表结构不断的补齐数据。针对以上过程,可以看出,Map输出的数据较大。一个属性的值就会有一个向量,并且这个向量中只有第d ~ e位的位图数据是用到的,其余的部分都是被置为0的,这样就有很大的数据冗余,Map数据量会增加网络I/O的负担,这就会影响索引建立的速度。
对于以上所述的不足,因此可以在Map过程中初始化一个较短的向量,向量的长度为块中记录条数,这样就减少了Map数据量的输出。同时还可以在Reduce过程中,进行数据的压缩,这样使得整个数据块形成的索引占用空间较少,下面介绍其细节。 如Algorithm 3和Algorithm 4。
Algorithm 3描述了Hadoop的Map过程,这个过程与Algorithm 1不同是在处理某一列中的一个属性值时,只建立一个块长度大小的向量,即建立非全列向量,而在Algorithm 1中,把全列其他值都置为0了,这些0是无用的,反而增加I/O开销。这样在块较大时,处理后Map的结果输出减少的比例是比较大的。比例大小与一个数据块占一列数据有很大关系,这种比例在处理数据量较大的时候反而减少的更多,即随着数据量增加,其减少数据的比例也是增加的。这就使得这种策略可扩展性较强。函数结果得到属性值和一个位图向量组成的( key,value) 键值对,即( Ti. Nij,( d,e,Vi) ) 。
Algorithm 4描述了Hadoop的Reduce过程,这个过程与Algorithm 2主要的不同之处是多了压缩的过程,同是为了减少空间,使用的编码方式正是上一节所介绍的ACOMPAX压缩编码,其压缩率较高, 同时在对数据进行查询处理的时所需IO负载有所降低,可以进一步提高数据查找的速度。
3实验与分析
为了测试方法的有效 性,实验使用 单节点, CPU: Intel( R) Pentium( R) CPU @ 3. 00 GHz,内存2 G。使用数据集是TPC-H[17]。数据集中lineitem表数据量大约占中数据量的75% 左右,是这个数据集主要数据部分,实验中我们首先对ACOMPAX进行压缩效率测试,选取的属性列的为quantity、discount和tax,其基数为分别50、11和9。下面测试了WAH和COMPAX两种压缩算法的压缩比,分别是quantity、discount和tax三种属性。 如图2 ~ 图4所示。
以图2可以看出,COMPAX的压缩率在在WAH上有了不少的提升,在一定的数据集之上甚至达到了30% 以上的提升,ACOMPAX在COMPAX的基础之上又有了一定的提升,在一定的数据集上有了接近20% 的空间节省。
图3、图4显示出ACOMPAX压缩率比WAH和COMPAX要高出不少,同时基数低的压缩率也比基数高的压缩率高,这点原因很简单,就是基数低,数据冗余更大。
下面在Hadoop平台上对位图索引的建立和查询时间进行实验分析。为了测试方法的有效性,实验使用的集群为11节点,1个主节点和10个从节点。CPU: Intel( R) Pentium( R) CPU @ 3. 00 GHz, 内存2 G,全部节点通过交换机相连接。使用的测试数据集是TPC-H。对于这个表中的16个属性中, 有5个是基数可能很大的列,我们依次对这个数据集中的11个基数较小的列建立了位图索引( 基数均不超过64) ,其使用了ACOMPAX编码方式。在表lineitem的DATE的三个属性上,我们把时间分割为年、月、日,这样三个基数为7( 年份跨度为7) 、 12和31,这样方便位图索引处理。首先是测试了WAH、COMPAX、ACOMPAX三种压缩 算法在Hadoop环境下建立位图索引所需时间,我们同样选取了quantity和tax。测试如图5、图6所示。
前面介绍了使用ACOMPAX压缩编码方式。从图5、图6可以看出建立索引时使用ACOMPAX编码方式相比于WAH和COMPAX方式的不同,由于ACOMPAX提供了更多的编码模板,但是在实际的编码时间 上面时间 相差甚小,在有些情 况下, ACOMPAX的编码方式使用的时间要小于WAH以及COMPAX编码方式,总体情况而言上面三种编码方式使用时间相当。
接着比较使用Hive和BMIH2的查询速度。关于Hive,使用的版本为Hive - 0. 9. 0,使用的配置数据库为mysql,同时为了验证有效性也在Hive上为需要进行查询速度比较的属性列上建立了索引。测试所使用的查询语句为TPC-H的查询语句,选取了其中的Q1、Q6和Q14,查询语句的位运算使用bit Vector型[4]的结构。并在Hive中对TPC-H的语句使用了Hive QL对标准语句进行了改写。下面是测试的图,结果如图7 ~ 图9所示。
图7 ~ 图9是Hive和BMIH2执行语句时间的比较,分别使用的是Q1、Q6、Q14语句,图8显示Hive和BMIH2在Q6语句上的执行时间进行了比较,这个语句WHERE语句稍有点复杂,执行时间和上图没有多大的差距。这里就可以看出位图索引的速查询度比单纯Hive要快出不少。
图7、图9显示出的比较结果是BMIH2的优势很明显,由于位图索引是使用的逻辑运算,省去了中间值的转换,这也是它快的一个原因,再者是因其数据量较小。
通过实验可看出,使用ACOMPAX压缩编码在Hadoop中建立位图索引的 速度方面 较WAH和COMPAX优势不够明显,但在占用空间上有一定的优势,其占用空间较过去的WAH和COMPAX有了不小的提高; 在Hadoop中的查询速度相比于Hadoop部件Hive的查询速度有不小的优势。
4总结
本文通过以位图索引为索引机制,并且在Hadoop平台上对改进的压缩编码进行了实现。其中的主要内容是: 基于Hadoop的位图索引策略具有很好的扩展性; 位图索引使用了ACOMPAX的压缩算法对数据进行压缩,使得索引的规模减小; 在进行索引处理时,进一步把查询操作转化成一系列的逻辑操作( 或与非) ,这使得处理的效率有提高,实验部分显示了位图索引的高效率和占用空间小的优势。 在一般的商用的数据库中,还有很多细节优化从而提升效率,比如数据分块,在索引块的设计,等等方面都需要进一步的优化,本文在这方面有一定的提升空间。
摘要：位图索引是一种使用Bit位的索引,有着较高的效率,大多运用于属性基数相对较小的情况。它有着较多的重复数据,可进行压缩,压缩编码的改进是研究的一个热点。对现有COMPAX编码方式进行改进。基于Hadoop的位图索引,使用分布式处理机制,使得位图索引的执行效率得到提升,可以运用于现今的大数据环境中;以解决目前大量的信息数据的查找问题。在建立索引过程中同时使用改进后的COMPAX编码进行数据压缩,使得索引占用空间减小,进一步提高对索引处理效率。
索引空间 篇5
关键词：嵌入式,GIS,网格索引,空间数据库
1 嵌入式系统
嵌入式系统[1]是先进的计算机技术、半导体技术、电子技术以及各种具体应用相结合的产物, 是技术密集、资金密集、高度分散、不断创新的新型集成知识系统。具有系统内核小、专用性强、系统精简、高实时性、多任务等诸多特点。
2 嵌入式GIS
2.1 基本概念
嵌入式GIS是可以运行在嵌入式计算机系统上高度浓缩、高度精简的GIS软件系统。与传统GIS技术相比, 新一代GIS技术在向跨平台、开发好、易集成、易渗透和融合好等方向发展, 而且价格低, 为地理信息技术融入其它信息技术提供了良好的技术基础。嵌入式GIS系统要求如下:1) 专有的空间数据存储和管理;2) 快速、高效的空间数据检索和分析;3) GPS支持, Web服务支持, 大型GIS系统的信息交换。
2.2 瓶颈问题
相比于大型GIS系统, 嵌入式GIS能够实现大部分功能, 比如:空间数据的管理、可视化、浏览、编辑、查询、检索、分析等功能, 但受设备性能等各方面条件限制, 其不能直接使用大型GIS系统的数据, 尤其是在数据量较大的情况下, 其效率的瓶颈问题更加突出, 因此必须基于嵌入式设备特点设计专门的格式, 适应嵌入式设备的I/O读取瓶颈, 同时由于一般的GIS平台在空间信息存储与运算时采用浮点数格式, 整个显示与运算是相当的耗费效率, 故迫切需要通过技术创新, 解决嵌入式GIS领域大数据量及高效率显示的问题。
3 空间库设计
通过对目前市场上已有的嵌入式GIS系统数据分析, 可知嵌入式设备中数据的组织和存储必须具备以下原则:1) 数据应当体现最小化原则, 并且可以高效的进行数据访问与操作;2) 不采用浮点数据的运算。在这个基本的原则下, 数据按照存储大小和非浮点格式存储。也就是数据按照一个数据包 (块) 的方式存储, 并且不采用浮点数据。
3.1 四分树存储结构
四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n×2n像元阵列的区域, 逐步分解为包含单一类型的方形区域, 最小的方形区域为一个栅格象元。四叉树中象元的尺寸是大小不一的, 位于较高层次的象限较大, 深度小即分解次数少, 而低层次上的象限较小, 深度大即分解次数多, 这反映了图上某些位置单一地物分布较广而另一些位置上的地物比较复杂, 变化较大。正是由于四叉树编码能够自动地依照图形变化而调整象限尺寸, 因此它具有极高的压缩效率。因为四分树的这个特性, 采用此种结构, 数据按照疏密度进行四分, 建立四分树索引结构, 可实现数据的快速读取和操作。
3.2 网格索引存储结构
网格索引存储结构, 通过一个规则格网来描述与每一个格网单元位置相对应的空间现象特征的位置和取值[2,3]。从空间组织上, 采取横向网格, 纵向多层。
3.2.1 数据分层
数据分层, 是根据一定的显示规则和要求, 结合数据自身特点, 将空间数据按照不同的显示比例尺, 组织成范围上重叠, 但在地图缩放操作时依次显示的空间立体结构。数据分层是对原始数据的概念提取, 可以较好的解决嵌入式设备的瓶颈和用户对地图操作效率的期望之间的矛盾。以在一个240X320的窗口内显示10万个点、线或者区为例, 从视觉的角度来看, 是无法区分10万个数据中的每一个数据, 此时对用户来讲, 数据的显示是没有意义的, 且此种情况下, 用户也无法进行有效的工作。相反, 在放大到已经级别下, 用户基本上可以辨识出地图中的线, 若进一步放大, 则图元的显示会更清晰, 这样用户就可以对地图进行有效操作, 因此, 用户必须在可以辨识数据的前提下才可以进行有效的工作。因此, 数据分层的主要思想是:在当前显示时, 使得显示的数据对用户最有意义。
3.2.2 数据分块
数据分块, 是指在同一各数据图层内, 地图数据被分割成一定范围的网格数据包, 在空间数据存储时即计算出每一个网格包的相对偏移地址, 按照一定的规则存储在空间数据库中。这样处理的目的是, 在进行地图的浏览和漫游时, 一方面可以避免整幅地图的数据读取与刷新, 另一方面可以根据预先计算的偏移量快速定位到需要显示的网格数据包, 读取数据, 从而可以有效减少I/O操作, 实现了地图数据的快速显示和刷新。
3.2.3 实际应用
基于上述空间库, 设计开发了新的移动GIS平台, 实现了大数据条件下的快速浏览与检索, 较好的解决了嵌入式设备上的瓶颈问题。
以某市城市管网巡检为例[4], 基本数据信息如下:
传统方式的空间信息存储, 文件最大在15M左右, 利用上述基于网格索引的空间信息数据库设计思路, 可以将上述大数据实现一次性装载。
4 结束语
随着嵌入式设备硬件性能的提升, I/O读取的瓶颈问题已经逐步得到缓解, 但基于上述网格索引的空间数据库设计思想依然有着重要的参考价值。
参考文献
[1]百度百科:嵌入式系统.
[2]班凯.嵌入式导航系统中空间信息数据模型研究.中国地质大学硕士学位论文, 2007.
[3]翻译:王秀群.网格是什么?——鉴别网格的三个指标.浙江大学计算机系.