摘要：自发地理信息(Volunteered Geographic Information, VGI)等在线GIS应用实现全球矢量数据的在线编辑与实时存取等功能,而现有的地理数据管理系统达到应用所需性能,因此设计和实现新的数据管理技术有很强的现实。研究二维矢量数据的多尺度表达与管理,了支持全球规模的矢量数据多尺度表达和即时更新的数据结构与算法,解决了VGI应用中存在的查询与更新效率低下等问题。现有的地理数据管理方法包括：分类、分层、分幅管理和基于关系模型或对象模型及二者混合的地理对象整体存储管理。前者不适用于VGI等在线系统,主要表现在：(1)尺度固定。各层次的数据是离散的,客户端缩放时,数据变化突然不够平滑；(2)对象分幅而被分割,整体性被破坏,影响应用；(3)制图综合由人工完成,数据更新牵涉到多层,一致性较难维护。地理对象整体存储的数据库系统具有ACID特性等优点,但其缺陷有：(1)太大的几何对象存取不便。(2)不具备动态多尺度的能力,仍需分层；(3)对象的更新是整体式的,不支持顶点的增量更新。(4)运行性能不高。上述问题,支持多尺度表达、拓扑一致更新的矢量数据管理方案。多尺度表达提升了可视化查询的处理效率,使在线浏览矢量数据可能。可视化查询包含截窗与简化两种操作,它可抽象化为一维或二维序列的范围top k查询(Range Top k Query)。分别使用笛卡尔树、DBLG-tree (Dynamic Binary Line Generapzation tree)、CDBLG-tree (Combinded Dynamic Line Generapzation tree)、缩放四叉树(Zoom QuadTree, ZQT)解决单权一维序列、多权一维序列、单权二维数据的范围top k查询,并给出了这些结构的更新方法。工作包括分析VGI应用的特点与需求、可视化查询并建立其与范围top k查询的联系、扩展已有的数据结构与表达模型并操作算法、实现了自发地理信息应用原型系统,具体分为以下几项：(1)了采样查询与可视化查询,对应于地理数据简化和截取简化操作,目的是限制数据查询结果的规模以加快传输、可视化、分析。将采样查询与可视化查询联系到经典的范围top k查询,建立并简化了问题。(2)DBLG-tree几何对象表达模型,并用于处理可视化查询。该结构具有更新性能可调整的特点。DBLG-tree是BLG-tree的扩展,后者是笛卡尔树的一个特例。DBLG-tree解决了单权一维序列范围top k查询问题。(3)以路径与拓扑点而不是以点集与边集来表达简单图的方法,并运用于表示几何对象构成的网络。实现方法是顶点分为拓扑顶点与几何顶点,分别以笛卡尔树与DBLG-tree表示。CDBLG-tree可处理拓扑与几何双权值的可视化查询。它解决了特定情况的双权值一维序列的top k查询问题。(4)基于MX-CIF四叉树的缩放四叉树,用于处理地理对象集的可视化查询。基于缩放四叉树结构CDBLG-tree可建立矢量数据金字塔。(5)整合以上的方法与技术,实现了矢量数据在线浏览与编辑的自发地理信息应用原型系统,该系统以全球一致化多层次高分辨率海岸线数据库(A Global Self-consistent, Hierarchical, High-resolution Shorepne Database, GSHHS)以及OpenStreetMap为实验数据集。在完成以上工作的中,本研究体现出的创新点包括：(1)VGI应用需求,定义了从原始数据集提取子集的采样操作,以及限制结果规模和采样误差的采样参数。采样操作与空间查询形成的可视化查询可抽象为一维或二维的范围top k查询(Range Top k Query),因而VGI数据多尺度表达可归结为各种条件的范围top k查询处理问题。(2)DBLG-tree及截窗查询、采样查询、可视化查询、子树操作、增量更新等算法。DBLG-tree可以高效处理儿何线对象的可视化查询,解决一维序列的范围top k查询问题。(3)CDBLG-tree表示几何对象形成的网络,并构造、查询与更新等处理算法,实现拓扑一致的空间网络数据可视化查询处理与更新。(4)了基于MX-CIF四叉树的缩放四叉树解决了二维地理数据范围top k查询问题。缩放四叉树和CDBLG-tree实现了地理对象保持整体结构的分块分层存储,并了矢量数据金字塔构建方法。关键词：空间数据库论文多尺度表达论文层次空间数据结构论文可视化查询论文范围top论文k查询论文拓扑一致化简论文CDBLG-tree论文增量更新论文
摘要5-8
Abstract8-11
目录11-13
章 引言13-37
1.1 研究问题的背景13-22
1.1.1 自发地理信息(VGI)简介13-14
1.1.2 VGI的产生背景及14-17
1.1.3 VGI系统的特点与数据管理问题17-21
1.1.4 本研究的必要性21-22
1.2 国内外研究现状及文献综述22-33
1.2.1 地理表达模型的研究现状23-24
1.2.2 空间数据库研究现状24-29
1.2.3 图形数据库研究现状29
1.2.4 自发地理信息的研究现状29-33
1.3 研究的内容与方法33-37
章 大型几何对象多尺度表达模型37-74
2.1 几何对象表示与查询37-47
2.1.1 几何对象表示方法37-38
2.1.2 采样查询与可视化查询38-41
2.1.3 线简化算法41-47
2.2 DBLG-TREE结构与性质47-52
2.2.1 BLG-tree功能47-49
2.2.2 DBLG-tree简介49-52
2.2.3 DBLG-tree的构造算法52
2.3 DBLG-TREE的查询52-58
2.3.1 截窗查询52-54
2.3.2 采样查询54-56
2.3.3 可视化查询56-57
2.3.4 DBLG-tree的子树操作57-58
2.4 DBLG-TREE的更新58-72
2.4.1 客户端数据更新的前提59-60
2.4.2 DBLG-tree结构不变更新60-62
2.4.3 子树重建代价分析62-65
2.4.4 滞后更新模式65-66
2.4.5 滞后更新的实现66-69
2.4.6 DBLG-tree更新算法69-72
2.5 小结72-74
章 特征保持的VGI数据多尺度表达模型74-105
3.1 地理对象概述74-86
3.1.1 地理对象的组成74-76
3.1.2 地理对象间的拓扑关系76-82
3.1.3 基于简单图的地理对象模型82-86
3.2 CDBLG-TREE简介86-91
3.2.1 CDBLG-tree表达模型86-89
3.2.2 CDBLG-tree的性质89-90
3.2.3 CDBLG-tree构建算法90-91
3.3 CDBLG-TREE查询与更新91-96
3.3.1 采样查询92
3.3.2 截窗查询92
3.3.3 可视化查询92-93
3.3.4 子树操作93-95
3.3.5 CDBLG-tree更新操作95-96
3.4 CDBLG-TREE方法及其推广96-104
3.4.1 范围K最值查询问题的推广97-98
3.4.2 CDBLG-tree的优化与扩展98-104
3.5 小结104-105
章 VGI矢量数据金字塔的构建与管理105-120
4.1 地理对象金字塔的架构105-113
4.1.1 基于四叉树的地理对象层次索引结构106-109
4.1.2 地理对象性权值计算109-112
4.1.3 地理对象分块112-113
4.2 基于磁盘设备的地理对象金字塔实现113-119
4.2.1 计算机存储系统结构特性113-114
4.2.2 三种分页方法114-116
4.2.3 访问模式与I/O效率116-118
4.2.4 外存化的CDBLG-tree操作算法118-119
4.3 小结119-120
第五章 VGI原型系统与实验120-135
5.1 自发地理信息原型系统实现120-129
5.1.1 自发地理信息应用的组成120-121
5.1.2 实验所用数据集简介121-123
5.1.3 实验原型系统123-127
5.1.4 实验原型系统分析127-129
5.2 DBLG-TREE的查询与更新实验129-134
5.2.1 实验结果图示130-133
5.2.2 实验结果分析133-134
5.3 小结134-135
第六章 总结135-137
6.1 论文总结135-136
6.2 研究展望136-137
本站原创