论文部分内容阅读
作者简介：曾凤生，男，仰恩大学计算机与信息学院讲师。研究方向：数据库应用，信息系统，电子商务。学 术 问 题 研 究 （综 合 版）
摘要：详细了解大数据的空间数据索引技术研究现状，对目前的一系列主要空间数据索引进行阐述。对现在的主流空间数据索引技术进行论述，依据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，那么一定数量的数据对就构成R-tree中的非叶子节点，然而其叶子节点则是由组成，指向空间数据库空间对象的标号由OI 表示。形式化表述该R-tree的索引结构为：
中间节点：(COUNT,LEVEL, < CP2, MBR2>,…, < CPM, MBRM>)
叶子节点：(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图的特点可总结为如下：
(1)给定一个数据集S，则其Voronoi图具有唯一性。
(2)如果Voronoi图的边数为ne，且其数据点为n个，则ne≤3n-6。
(3)所有Voronoi凸多边形的边数不超过6。同时，在一个Voronoi图中，平均每个Voronoi多边形的邻居数不超过6。kNN查询在过滤有效的候选集的时候利用了该特性，提高了其效率。故该特性具有重要的作用。
在求解近邻查询等问题的时候，Voronoi图的以上几个特性起到了非常重要的作用，使这些问题变得易于解决。因此，在空间数据中根据Voronoi图的特性构建的索引结构被广泛应用。
5 空间填充曲线
1890年，意大利学者皮亚诺首次提出空间填充曲线理论，次年著名数学家希尔伯特对其进行修改和完善，空间填充曲线以其优异的性能被大量学者深入研究，并被广泛应用于各个领域⑨。空间填充曲线的提出是为了找出将多维数据空间“填满”的曲线，该曲线能按照相应的填充规则，通过有限次逼近方法，将某个多维数据大空间划分为很多个体积较小的网格，且总是存在着一条能贯穿所有网格的连续空间填充曲线，且空间填充曲线贯穿任何一个网格有且仅有一次。同时空间填充曲线按照线性顺序还对这些高维空间中的网格进行一对一编号。
空间填充曲线的实质从数学上看，是线段到整个d维欧式空间的一种连续映射，即线段上的每一等份与整个d维立方体中的格子一一对应，精度可以通过曲线的逼近次数k进行控制。对于d维单位超立方体［0,1］d 和一维单位线段［0,1］，空间填充曲线实现了如下形式的连续映射：
f:［0,2kd-1］→［0,2k-1］d(k≥1,d≥2)
映射关系表明，d维单位超立方体空间通过k次逼近，每一维划分为2k等份，整个空间划分为2kd个小方格，小方格和划分为2kd等份的［0，1］线段一一对应。最典型的映射函数包括Gray曲线、Z曲线和Hilbert 曲线。以上3 种空间填充曲线中，在数据聚类特性方面，最优是Hilbert 空间填充曲线，最差的是Z 空间填充曲线，但是Hilbert 空间填充曲线的映射算法的执行过程最复杂，而Z 空间填充曲线的映射算法的执行过程最简单。
Gray曲线与Hilbert曲线有类似之处，如一阶的Gray曲线与一阶的Hilbert曲线的填充规则几乎相同，但高阶的Gray曲线则有自己的特点。对于一个i阶的Gray曲线，需要将(i-1)阶Gray曲线进行必要的旋转，且必须要(i-1)阶Gray曲线的网格替换掉一阶的Gray曲线。i阶的Gray曲线的旋转具体情况如下：在G0和G3中的(i-1)阶曲线没有变化，在G2中的(i-1)阶曲需在原平面逆时针旋转180°，而在G1中的(i-1)阶曲线需在原平面顺时针旋转180°。
Z曲线的最简单形式为一条阶为1和2×2大小的网格的曲线，图5(a)所示的为Z曲线的最简单形式。而2 阶 Z 曲线的形状如图 5(b)所示。i阶Z曲线的构造必须将最简单的 Z曲线中的每一个网格用(i-1)阶Z 曲线进行替换。
a)一阶Z曲线b)二阶Z曲线
图5：Z曲线
Hilbert曲线是由德国数学家David Hilbert提出的，与Z-ordering曲线空间填充曲线类似，图6展示了Hilbert曲线的生成过程。由图可知，Hilbert曲线是没有斜线的，故其排序方式较Z曲线优越，且能直观地放映出空间数据之间的近邻关系，不过其计算量相比Z曲线复杂一些。
a)一阶Hilbert曲线 b)二阶Hilbert曲线
图6：Hilbert曲线
6结论
在物联网技术和移动设备的定位服务迅速发展并被广泛应用的背景下，空间数据索引的社会需求越来越多，也吸引着越来越多的学者对大数据的空间数据索引进行研究。本文对空间数据索引的相关概念进行详细阐述和分析，还对空间数据索引中的R-tree索引、哈希索引、Voronoi图索引和空间填充曲线进行详细阐述，并指明其各自特点。目前的空间数据索引技术虽然很多，但根据我国大数据的具体情况所进行的研究尚存不足，因此，本研究可为空间数据索引技术研究提供一定的理论基础。
注释：
① 严霄凤,张德馨. 大数据研究. 计算机技术与发展［J］.2013,23(4):168-172.
② ④ ⑦ 杨宇曦. 空间数据索引技术的研究及在GIS中应用［D］.工学硕士学位论文, 大连理工大学，2005.
③ 徐红波. 基于空间填充曲线高维空间查询算法研究［D］.工学博士学位论文, 哈尔滨理工大学，2010.
⑤ ⑧ 董亭亭. 大数据下空间数据索引和kNN查询技术的研究［D］.工学硕士学位论文, 大连理工大学，2013.
⑥ 余登峰. 基于R树的空间数据索引研究和实现［D］.工学硕士学位论文, 中国地质大学， 2006.
⑨ Zhihua Qu, J. F. Dorsey, D. M. Dawson. Model Reference Robust Control of a Class of SISO Systems［J］. IEEE Transactions on Automatic Control, 1994, 39(11): 2219-2234.
刘胤田,唐常杰,曾涛等. 基于空间填充曲线的数据分发区域匹配. 系统仿真学报［J］.2007，(02).
The Research of Spatial Data Indexing on Large Scale Data
ZENG Feng-sheng
（Yang-En University, 362014 Quanzhou, Fujian, China）
Abstract:In this paper, the status quo of spatial date index research on large scale data is studied, and a series of major spatial data index at present are expounded. Based on the principle of the R-tree index, Hash index, Voronoi map index and Space filling curve, this paper discusses upon the mainstream of the spatial data index technology fully and analyzes their characteristics in nature so as to provide the foundation theoretical basis for the spatial date index research on large scale data.
Key words: Large-scale Data; Spatial-data Index; R-tree Index; Hash Index; Space-filling【责任编辑罗雪】
摘要：详细了解大数据的空间数据索引技术研究现状，对目前的一系列主要空间数据索引进行阐述。对现在的主流空间数据索引技术进行论述，依据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图的特点可总结为如下：
(1)给定一个数据集S，则其Voronoi图具有唯一性。
(2)如果Voronoi图的边数为ne，且其数据点为n个，则ne≤3n-6。
(3)所有Voronoi凸多边形的边数不超过6。同时，在一个Voronoi图中，平均每个Voronoi多边形的邻居数不超过6。kNN查询在过滤有效的候选集的时候利用了该特性，提高了其效率。故该特性具有重要的作用。
在求解近邻查询等问题的时候，Voronoi图的以上几个特性起到了非常重要的作用，使这些问题变得易于解决。因此，在空间数据中根据Voronoi图的特性构建的索引结构被广泛应用。
5 空间填充曲线
1890年，意大利学者皮亚诺首次提出空间填充曲线理论，次年著名数学家希尔伯特对其进行修改和完善，空间填充曲线以其优异的性能被大量学者深入研究，并被广泛应用于各个领域⑨。空间填充曲线的提出是为了找出将多维数据空间“填满”的曲线，该曲线能按照相应的填充规则，通过有限次逼近方法，将某个多维数据大空间划分为很多个体积较小的网格，且总是存在着一条能贯穿所有网格的连续空间填充曲线，且空间填充曲线贯穿任何一个网格有且仅有一次。同时空间填充曲线按照线性顺序还对这些高维空间中的网格进行一对一编号。
空间填充曲线的实质从数学上看，是线段到整个d维欧式空间的一种连续映射，即线段上的每一等份与整个d维立方体中的格子一一对应，精度可以通过曲线的逼近次数k进行控制。对于d维单位超立方体［0,1］d 和一维单位线段［0,1］，空间填充曲线实现了如下形式的连续映射：
f:［0,2kd-1］→［0,2k-1］d(k≥1,d≥2)
映射关系表明，d维单位超立方体空间通过k次逼近，每一维划分为2k等份，整个空间划分为2kd个小方格，小方格和划分为2kd等份的［0，1］线段一一对应。最典型的映射函数包括Gray曲线、Z曲线和Hilbert 曲线。以上3 种空间填充曲线中，在数据聚类特性方面，最优是Hilbert 空间填充曲线，最差的是Z 空间填充曲线，但是Hilbert 空间填充曲线的映射算法的执行过程最复杂，而Z 空间填充曲线的映射算法的执行过程最简单。
Gray曲线与Hilbert曲线有类似之处，如一阶的Gray曲线与一阶的Hilbert曲线的填充规则几乎相同，但高阶的Gray曲线则有自己的特点。对于一个i阶的Gray曲线，需要将(i-1)阶Gray曲线进行必要的旋转，且必须要(i-1)阶Gray曲线的网格替换掉一阶的Gray曲线。i阶的Gray曲线的旋转具体情况如下：在G0和G3中的(i-1)阶曲线没有变化，在G2中的(i-1)阶曲需在原平面逆时针旋转180°，而在G1中的(i-1)阶曲线需在原平面顺时针旋转180°。
Z曲线的最简单形式为一条阶为1和2×2大小的网格的曲线，图5(a)所示的为Z曲线的最简单形式。而2 阶 Z 曲线的形状如图 5(b)所示。i阶Z曲线的构造必须将最简单的 Z曲线中的每一个网格用(i-1)阶Z 曲线进行替换。
a)一阶Z曲线b)二阶Z曲线
图5：Z曲线
Hilbert曲线是由德国数学家David Hilbert提出的，与Z-ordering曲线空间填充曲线类似，图6展示了Hilbert曲线的生成过程。由图可知，Hilbert曲线是没有斜线的，故其排序方式较Z曲线优越，且能直观地放映出空间数据之间的近邻关系，不过其计算量相比Z曲线复杂一些。
a)一阶Hilbert曲线 b)二阶Hilbert曲线
图6：Hilbert曲线
6结论
在物联网技术和移动设备的定位服务迅速发展并被广泛应用的背景下，空间数据索引的社会需求越来越多，也吸引着越来越多的学者对大数据的空间数据索引进行研究。本文对空间数据索引的相关概念进行详细阐述和分析，还对空间数据索引中的R-tree索引、哈希索引、Voronoi图索引和空间填充曲线进行详细阐述，并指明其各自特点。目前的空间数据索引技术虽然很多，但根据我国大数据的具体情况所进行的研究尚存不足，因此，本研究可为空间数据索引技术研究提供一定的理论基础。
注释：
① 严霄凤,张德馨. 大数据研究. 计算机技术与发展［J］.2013,23(4):168-172.
② ④ ⑦ 杨宇曦. 空间数据索引技术的研究及在GIS中应用［D］.工学硕士学位论文, 大连理工大学，2005.
③ 徐红波. 基于空间填充曲线高维空间查询算法研究［D］.工学博士学位论文, 哈尔滨理工大学，2010.
⑤ ⑧ 董亭亭. 大数据下空间数据索引和kNN查询技术的研究［D］.工学硕士学位论文, 大连理工大学，2013.
⑥ 余登峰. 基于R树的空间数据索引研究和实现［D］.工学硕士学位论文, 中国地质大学， 2006.
⑨ Zhihua Qu, J. F. Dorsey, D. M. Dawson. Model Reference Robust Control of a Class of SISO Systems［J］. IEEE Transactions on Automatic Control, 1994, 39(11): 2219-2234.
刘胤田,唐常杰,曾涛等. 基于空间填充曲线的数据分发区域匹配. 系统仿真学报［J］.2007，(02).
The Research of Spatial Data Indexing on Large Scale Data
ZENG Feng-sheng
（Yang-En University, 362014 Quanzhou, Fujian, China）
Abstract:In this paper, the status quo of spatial date index research on large scale data is studied, and a series of major spatial data index at present are expounded. Based on the principle of the R-tree index, Hash index, Voronoi map index and Space filling curve, this paper discusses upon the mainstream of the spatial data index technology fully and analyzes their characteristics in nature so as to provide the foundation theoretical basis for the spatial date index research on large scale data.
Key words: Large-scale Data; Spatial-data Index; R-tree Index; Hash Index; Space-filling【责任编辑罗雪】