POI简化并行计算方法研究

论文摘要

随着移动互联网的发展和智能设备的普及,用户越来越多的关注自己的位置信息,实时准确的位置信息正在成为用户最渴求的信息之一,用户在关注其位置信息的同时,也关注其周围的其它基础地理信息,各种基于LBS (Location Based Service)的应用软件广受用户的欢迎,手机地图也成为智能手机的必备软件,各IT信息服务商,也都推出其地图在线搜索服务。POI (Points of Interest),兴趣点,涵盖了餐饮、娱乐、金融机构、旅游景点、地标建筑、加油站、停车场等人们日常生活中最为经常的基础信息,POI数据的准确性,属性的丰富程度、表达的清晰度及其实时显示效率都将影响移动地图的质量与可用性效果。但当前POI表达存在许多问题,特别是在用户搜索特定信息时,由于查询结果数据量较大,会产造成某几个区域POI的重叠、压盖等,进而影响用户的对地理空间的认知,降低地图的可用性。针对此问题,本文提出了面向POI简化的并行算法。本文的研究内容与成果主要包括以下几部分：1、分析了当前网络地图中POI的表达特点,总结了当前POI表达常用的方法；结合点要素综合质量评价指标,提出了描述POI基本信息的指数与POI简化的质量评价指标。分析了点要素简化算法的效率与质量。结合POI对简化算法的需求,遴选了适合POI简化的算法。2、总结了常用的并行方法设计方法,改进了“圆”增长算法、居民地空间比率算法。提出“圆”增长算法、居民地空间比率算法对数据划分方法的要求,结合POI与道路的关系,提出基于道路网眼层次结构分解的POI简化并行计算方法。3、设计了POI简化并行的实验平台,基于此平台编程实现了基于道路网眼层次结构分解的POI简化并行算法,以及改进后“圆”增长算法、居民地空间比率算法的任务并行计算方法。使用不同规模的POI数据与道路数据对算法进行了测试、统计与分析,分析了算法的执行效率与综合质量,结果证明该数据并行计算方法满足了POI简化对效率与质量的需求。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 选题背景及研究意义
• 1.1.1 选题背景
• 1.1.2 研究意义
• 1.2 国内外研究现状
• 1.2.1 点要素简化算法
• 1.2.2 点要素综合质量评价方法
• 1.2.3 并行计算及其在地图综合中应用
• 1.3 POI简化并行计算研究存在问题
• 1.4 本文研究内容、技术路线及章节安排
• 1.4.1 研究内容
• 1.4.2 技术路线
• 1.4.3 章节安排
• 第2章 POI表达及对简化的要求
• 2.1 POI的分类及其表达
• 2.1.1 POI分类
• 2.1.2 POI的表达形式
• 2.1.3 POI的表达特点
• 2.2 POI表达对简化需求
• 2.2.1 POI表达存在的问题
• 2.2.2 POI表达对简化的需求
• 2.3 POI简化质量评价指标
• 2.3.1 地图综合质量评价指标
• 2.3.2 点要素简化综合评价指标
• 2.3.3 适合POI简化质量评价指标
• 2.4 本章小结
• 第3章 适合POI简化的点要素简化算法可用性分析
• 3.1 算法效率分析的基础理论
• 3.1.1 算法效率分析中常用的数学符号
• 3.1.2 算法时间复杂度分析的常用方法
• 3.2 点要素简化算法的效率与质量分析
• 3.2.1 居民地空间比率算法
• 3.2.2 重力模型算法
• 3.2.3 分布系数算法
• 3.2.4 “圆”增长算法
• 3.2.5 基于凸壳的简化方法
• 3.2.6 保持空间分布特征的群点简化方法
• 3.2.7 基于遗传算法的点群目标选取模型
• 3.2.8 逼近算法
• 3.2.9 基于Circle特征变换的点群选取算法
• 3.2.10 基于Kohonen网络的点群综合方法
• 3.2.11 基于圆增长特征的点状要素选取算法
• 3.2.12 基于Voronoi图的点群综合算法
• 3.3 适合POI简化算法的确定
• 3.4 本章小结
• 第4章 POI简化并行算法分析与设计
• 4.1 并行算法设计方法
• 4.2 点要素简化算法并行化
• 4.2.1 居民地空间比率算法并行化
• 4.2.2 分布系数算法并行化
• 4.2.3 “圆”增长算法的并行化
• 4.3 基于道路网眼层次结构分解的数据划分方法
• 4.3.1 面向POI简化并行计算的数据划分原则
• 4.3.2 基于道路网眼层次结构分解的数据划分方法
• 4.4 本章小结
• 第5章 POI简化并行计算实验
• 5.1 实验环境
• 5.1.1 并行编程环境概述
• 5.1.2 Pthread概述
• 5.1.3 实验平台
• 5.2 POI简化算法的并行算法概述
• 5.2.1 道路网眼层次结构构建算法
• 5.2.2 基于Pthread的POI简化并行算法概述
• 5.3 基于任务分解的POI简化并行计算实验
• 5.3.1 实验数据
• 5.3.2 “圆”增长算法任务并行化实验及其结果分析
• 5.3.3 居民地空间比率算法任务并行化实验及其结果分析
• 5.4 基于道路网眼层次结构划分的POI简化并行计算实验
• 5.4.1 实验数据
• 5.4.2 基于道路网眼层次结构划分实验
• 5.4.3 POI简化并行计算实验及其结果分析
• 5.5 本章小结
• 第6章 结论与展望
• 6.1 结论
• 6.2 展望
• 参考文献
• 攻读硕士期间科研成果
• 致谢