大规模空间数据的自适应Geohash剖分与编码

论文总字数：24019字

摘 要

论文作者签名： 焦凤伟 导师签名： 童蔚苹 日期 2019年5月29日

摘 要

随着互联网的发展，GPS、物联网等被广泛应用，空间数据的规模正在快速增长，并且随着需求的多样化与细分化，空间数据的存储呈现出复杂化的趋势。如何对海量、复杂的空间数据高效存储、管理已经成为亟待解决的问题。NoSQL数据库的出现为大量空间数据的存储提供了新的解决方案。

本文针对目前空间数据管理的不足，使用OSM轨迹点数据，基于HBase分布式数据库，主要做了以下工作：

（1）分析了HBase的架构和技术原理，设计空间点数据的存储模型，为后续索引和查询算法的设计奠定基础。

（2）设计自适应Geohash索引，对Geohash编码进行改进，设计制定单元自适应分裂条件(阈值)，阈值的设定基于工程与实验得到的经验，考虑OSM轨迹点数据的点的数据与满四叉树节点个数相等时的树的深度作为合理值。数据单元区别于将经度纬度进行类二分法划分，而是四分为子单元，相当于进行了两次划分，以此类推，往下有些叶子节点下没有数据，有些叶子节点在区域空间对象少于阈值时没有继续划分。

（3）设计范围查询，将空间矩形转换为一系列对应的Range，然后按照HBase中Rowkey的设计模式将查询的空间Range构成对应的Rowkey范围。一个行键对应一次Scan操作，这样生成的行键对数量即为从HBase数据库中读取数据的次数，大大减小了通信开销。

关键词：HBase；空间数据;空间索引;Geohash

Abstract

With the development of the Internet, GPS and the Internet of Things are widely used. The scale of spatial data is growing rapidly, and with the diversification and segmentation of demand, the storage of spatial data presents a trend of complexity. How to efficiently store and manage massive and complex spatial data has become an urgent problem to be solved. The emergence of NoSQL databases provides a new solution for the storage of large amounts of spatial data.

In view of the shortcomings of current spatial data management, this paper uses OSM track point data, based on HBase distributed database, and mainly do the following work:

(1) Analyze the architecture and technical principle of HBase and design the storage model of spatial point data, which lay the foundation for the design of spatial index and query algorithm .

(2) An adaptive Geohash index is designed to improve Geohash coding. Design and formulate unit adaptive splitting condition (threshold value), which is set based on the experience of engineering and experiment. Considering the point data of OSM track point data and the full quadtree when the number of nodes is equal, the depth of the tree is taken as a reasonable value. The data unit is different from the dichotomy of the longitude latitude, but is divided into sub-units, which is equivalent to two divisions, and so on. There are no data under some leaf nodes, and some leaf nodes have fewer objects in the regional space. There is no further division at the threshold.

(3) To design range query, convert the space rectangle into a series of corresponding Range, and then according to the Rowkey design pattern in HBase, the query space Range constitutes the corresponding Rowkey range. A row key corresponds to a Scan operation, and the number of row key pairs generated is the number of times when data is read from the HBase database, which greatly reduces communication overhead.

KEY WORDS: HBase; Spatial data; Spatial index: Geohash

目 录

摘 要 I

Abstract II

第一章 绪论 1

1.1 研究背景与意义 1

1.2 国内外研究现状 1

1.3 主要内容及章节安排 3

1.3.1 主要研究内容 3

1.3.2 论文的章节安排 3

第二章 基于HBase的空间数据存储设计 5

2.1 HBase分布式数据库 5

2.1.1 HBase架构 5

2.1.2 HBase数据与存储模型 5

2.1.3 HBase接口介绍 6

2.2 空间数据存储设计 7

2.2.1 空间对象的几何属性 7

2.2.2 空间对象的空间参考 8

2.2.3 空间对象的表存储 9

2.3 本章小结 10

第三章 自适应Geohash索引设计 11

3.1 空间索引 11

3.1.1 格网索引 11

3.1.2 四叉树索引 11

3.1.3 K-d(k-dimentional tree)树索引 11

3.1.4 R树索引 12

3.1.5 空间填充曲线 12

3.2 Geohash概述 14

3.2.1 Geohash的划分与编码 15

3.2.2 Geohash的特点 16

3.3 自适应Geohash索引设计 16

3.4 基于Geohash的索引表的设计 17

3.5 本章小结 17

第四章 范围查询实验及结果分析 18

4.1 范围查询 18

4.1.1 概念 18

4.1.2 关键技术 18

4.1.3 查询方案设计 19

4.2 实验测试与分析 21

4.2.1 软硬件环境 21

4.2.2 测试数据 21

4.2.3 范围查询效率 21

4.3 本章小结 21

第五章 总结与展望 22

5.1 总结 22

5.2 展望 22

参考文献 23

致 谢 25

剩余内容已隐藏，请支付后下载全文，论文总字数：24019字