原创《大数据空间数据索引技术》：关于免费索引论文范文在这里免费下载与阅读,为您的索引相关论文写作提供资料。
作者简介：曾凤生,男,仰恩大学计算机和信息学院讲师.研究方向：数据库应用,信息系统,电子商务.学 术 问 题 研 究 （综 合 版）
摘 要：详细了解大数据的空间数据索引技术研究现状,对目前的一系列主要空间数据索引进行阐述.对现在的主流空间数据索引技术进行论述,依据R-tree索引、哈希索引、Voronoi图索引和空间填充曲线的原理,从其本质上分析其各自特点,从而为大数据的空间数据索引技术研究提供理论基础.
关键词：大数据；空间数据索引；R-tree索引；哈希索引；空间填充曲线
中图分类号：C37文献标识码：A 文章编号：0000-0129/K（2014）01-0097-041 引言
近年来,随着物联网和移动互联网的迅猛发展,给人们带来了诸多便利,同时也给计算机网络带来越来越多数据存储和处理的困难.移动互联网的普及,使用的用户越来越多,用户上传到计算机网络的图片和视屏数据也就越来越多,和此同时,用户也对各自的图片和视屏数据进行分享和传播,物联网技术使用数以万计的传感器,也获取到巨大的数据量,移动设备和电脑等也都在分享和传播大量数据,这就造成全球数据的爆炸式增长①.据专家统计,2013年的全球数据量是2005年的8倍.目前,物联网和移动互联网都以惊人的速度发展,故专家推测,到2020年,全球数据规模将是现在的20倍.大数据中很大一部分来自移动互联网的地理位置、航空航天遥感以及各种经济社会统计等,这些数据属于大数据的空间数据.这些数据的复杂度比较高,且更新速度快,因此,对作为大数据处理核心的空间数据索引技术进行研究,具有重要的社会价值②.
空间数据索引是一种根据空间中目标对象的形状和位置,或空间中目标对象之间的空间相对关系③,并按某种关系进行排列的一种数据结构.根据其集合特征,空间数据分为点、线、区域等几种主要类型.由于空间数据索引应用的普遍性和重要性,大量国内外学者对其进行了深入研究,目前已经获得了很多种空间数据索引技术,并根据各自的技术特性,应用于各个领域.虽然空间数据索引技术很多,但它们基本都是由B树索引、二叉树索引、哈希函数等发展而来④.空间数据索引主要分为四种： B-tree的索引,二叉树的索引,空间目标排序法和Hashing的索引技术.本文具体总结和分析了大数据中的空间数据索引相关概念,对空间数据索引中的R-tree索引、哈希索引、Voronoi图索引和空间填充曲线进行详细阐述,指明其各自特点.
2 R-tree索引
R-tree索引是Guttman在八十年代提出的一种将B-tree索引技术拓展到多维情况下的索引技术,由于其具有高效索引结构的特点,被广泛应用于大数据的空间索引中⑤⑥.
在R-tree索引技术中,索引记录项必须被叶子节点所包含,再通过相关二元组管理不同的空间数据对象.如果某R-tree的阶数为M,那么一定数量的数据对
中间节点：(COUNT,LEVEL,
叶子节点：(COUNT,LEVEL,
当R-tree索引结构为二维空间的时候,情况则有所不同,如图1所示的二维空间的R-tree实例中,该树的所有叶子都在同一层.从R-tree的结构图可知,R-tree索引的效率和外存页面的存放策略、以及索引对象息息相关.在R-tree的索引结构扩展到n维空间时,如果索引对象的重叠率太大,则需要通过很多条查询路径才能最终查询到目标数据对象,然而其中很多条查询路径却并不包括目标数据对象,这就造成整个查询效率任务繁重,但效率低下.故R-tree索引技术的索引效率取决于空间数据对象的矩形区域之间的覆盖率和重叠率.
图1：二维空间的R-tree结构示意图
为提高R-tree索引技术的索引效率,学者将MapReduce模型应用于索引技术中,提出基于MapReduce模型的R-tree索引创建,将R-tree索引推向并行化.其思想是先用分区算法将数据划分为多个子数据区域,再将这些子数据区域同时进行R-tree索引,最后再将各个子数据区域获得的子R-tree进行合并,形成最终的R-tree.由于R-tree的层次型结构不易分散化,使得该索引结构的可扩展性不高.
3 哈希索引
哈希索引是指利用哈希函数对空间数据进行定位的索引技术,该索引技术被广泛应用于空间数据索引中.其中可扩展的哈希索引结构主要分为动态哈希网格R文件和网格文件两种⑦⑧.
图2：网络文件结构
网格文件根据数据空间的正交网格将整个数据空间划分为若干个子空间网格,再根据数据空间的每一维区域上的刻度将各个子空间网格组成对应目录,并对每一个子空间网格进行标识,将网格之间的关系和目录单元进行一一对应.将网格单元中的空间数据存放在和其对应的目录项中,当数据不断增加时,网格目录中的信息量也随之增加,故目录信息应存放在硬盘中.由上可知,任何网格单元会有一个用于指向存放对应数据对象详细信息的外存页面的地址,为了提高索引效率,根据网络刻度和标识的占用空间较小的特点,将它们直接存在内存中,再根据哈希方法获取网格的访问地址,故哈希索引只需要两次输入/输出就可以准确地查找到的目标记录,这样就能确保磁盘的访问次数不会太大.如图2所示的网格文件结构.
R文件是从网络文件改进而来,两者具有一定程度的相似性,但也各有特点.R文件主要是用来索引空间数据中的非点状和点状目标,不会产生对空间目标进行映射和空间目标的裁剪或者重复存储.
4 Voronoi图索引
作为几何学的一种重要图理论,Voronoi图被广泛应用且成功地解决各种数学问题,如：最大空圆问题、最小数问题、凸包问题以及最近点问题.Voronoi图理论可简单描述为：在某一个平面上,任意分布着几个点,根据这些点的位置和相应规则,将整个平面划分为多个子部分,以获得若干个多边形的平面分割图.
图3：Voronoi图
n个点分布在平面上,点集合S等于{p1, p2,等, pn},在该集合中任意选取两个点pi和pj,作出这两个点连线的中垂线,该中垂线将整个平面分成两个子平面,用H(pi, pj)表示点pi所处的子平面,则另一个子平面包含pj点,其用H(pj, pi)表示.用V(pi)表示点pi所处子平面的多边形区域,则该Voronoi多边形的边数最多为n-1,其表示和另外的点相比,和pi点更近的区域.如图4所示,设定n为6,则和p1关联的Voronoi多边形域为4边形.
图4：Voronoi多边形图
一个Voronoi图中,有n个对象点构成的空间数据集S,其结构用Vor(S)表示,则该图中就有n个Voronoi凸多边形分别一一对应着n个对象点,这些凸多边形的每条边都是由对应两个对象点之间的中垂线构成,且每条边都是由两个Voronoi凸多边形共同拥有,而这些边之间的交点构成了Voronoi凸多边形的顶点.Voronoi图的特点可总结为如下：
索引论文参考资料：
结论：大数据空间数据索引技术为关于对写作索引论文范文与课题研究的大学硕士、相关本科毕业论文一本书的索引是什么论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。
