多环境下Skyline计算问题研究

发布时间：2017-04-09 10:10

  本文关键词：多环境下Skyline计算问题研究，，由笔耕文化传播整理发布。

【摘要】：Skyline计算,也称轮廓查询,本质是一个多目标优化问题,目的旨在发现给定数据集中所有用户可能感兴趣的信息。作为一种基础的数据操作方法,Skyline计算在多目标决策支持系统、导航系统、环境监控、数据挖掘等领域有着广泛的应用。因此,自2001年被提出以来,Skyline计算研究一直是数据库和数据挖掘领域许多研究者关注的焦点。Skyline查询算法的设计主要受三个因素影响：数据特征、运行环境和设计目标。数据特征包含数据的生成方式、存储结构、空间维度及规模等信息。运行环境指执行查询操作的计算和网络环境,分集中式和分布式两种。设计目标则包括执行效率、渐进性、公平性、友好性等指标。三种因素的交织造成了Skyline计算环境的复杂多样性。目前,已有多种Skyline算法被相继提出,涵盖了静态和动态数据、固定和移动对象、集中和分布式系统、低维和高维数据空间等不同环境。不过,随着近年来云计算、传感网、大数据、移动互联等技术的飞速发展,新的应用环境和需求不断涌现,同时也对以往相对成熟的环境带来了影响。面对这种情况,现有算法已难以适应发展的需要。本文针对多种环境下的Skyline计算问题进行了研究与探索,主要研究点包括：集中式静态数据集下算法效率的提升问题；移动环境中基于位置依赖的连续查询问题；分布式架构下的Skyline计算问题和集中式静态数据集上的反Skyline查询问题。主要贡献如下：(1)在集中式静态数据集环境下,为提升大规模、高维数据集的Skyline计算效率,从算法自身和计算平台等方面考虑,提出了两种基于多核并行技术的Skyline算法。第一种算法采用预排序策略,将数据集按照任意指定维度排序,然后划分为多个子集进行并行化处理。第二种算法在第一种算法的基础上,首先改进了预排序策略,然后通过选择枢轴点,将数据空间划分为若干区域,利用区域支配关系,减少数据对象之间的支配测试次数,进一步提高了效率。两种算法处理过程简洁,具有较好的渐进性、用户友好型和可扩展性。实验结果表明,对于规模较大、维数较高的数据集,计算效率有较大提升。(2)在移动环境下,针对查询点快速移动时连续、高效输出指定搜索区域Skyline集合的问题,结合数据流技术,提出一种基于位置依赖的连续查询算法。首先使用R-树快速更新查询数据,然后利用两次连续计算时搜索区域的重叠性构造被动数据流,并对新增和失效数据分别进行处理,最终连续输出Skyline集合。由于充分利用了已有计算结果,算法计算量有大幅下降。实验结果表明,该算法特别适合计算频度要求较高的场合,与基于网格索引的算法相比,时间效率随着数据集规模的增大提升明显。(3)在分布式环境下,针对层次化拓扑结构对等网,研究了分布式数据流环境下的Skyline计算问题,提出了一种由下往上分层汇聚结果的算法。对下层网络,通过构造路由树重建了的路由结构,保证在每一跳均能对传输的数据进行有效过滤,降低了计算和通信开销;对上层网络,采用保序映射的方式将多维数据转换到一维空间并排序,然后依据上层网络节点标识符的大小顺序计算,保证了算法的渐进性和效率。实验结果表明,算法具有较好的可扩展性和较小的通信代价。(4)针对应用需求的变化,研究了集中式静态数据集下的反Skyline计算问题,以经典算法BBRS为基础,提出一种改进算法。预先为数据集建立R-树索引,然后以查询点为中心将数据空间分割为若干独立区域,使用一种简单的窗口查询方法并利用多核并行技术加速算法运行。实验结果表明,相对于传统的算法,算法性能有一定提升。
【关键词】：轮廓查询 多核并行 位置服务 层次化对等网 反轮廓查询
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要5-7
• ABSTRACT7-12
• 符号对照表12-13
• 缩略语对照表13-17
• 第一章 绪论17-29
• 1.1 研究背景17-19
• 1.2 Skyline计算基本概念19-22
• 1.2.1 形式化定义19-20
• 1.2.2 基本算法BNL20-21
• 1.2.3 算法评价标准21-22
• 1.3 研究现状22-26
• 1.3.1 集中式环境下的Skyline计算22-24
• 1.3.2 数据流环境下的Skyline计算24-25
• 1.3.4 分布式环境下的Skyline计算25-26
• 1.3.5 其它类型Skyline计算26
• 1.4 挑战性问题26-27
• 1.5 研究内容及贡献27-28
• 1.6 论文章节安排28-29
• 第二章 多核并行Skyline计算29-55
• 2.1 引言29
• 2.2 背景知识29-34
• 2.2.1 相关工作29-30
• 2.2.2 多核并行计算30-33
• 2.2.3 Skeletal并行编程模型33-34
• 2.3 采用预排序策略的并行Skyline算法34-41
• 2.3.1 预排序策略34-35
• 2.3.2 算法流程35-36
• 2.3.3 详细实现36-38
• 2.3.4 算法分析38-39
• 2.3.5 实验验证39-41
• 2.4 采用枢轴选择策略的并行Skyline算法41-53
• 2.4.1 枢轴点及区域支配41-43
• 2.4.2 算法流程43
• 2.4.3 详细实现43-46
• 2.4.5 算法分析46-47
• 2.4.6 实验及分析47-53
• 2.5 小结53-55
• 第三章 移动环境中的Skyline计算55-69
• 3.1 引言55
• 3.2 问题描述55-56
• 3.3 背景知识56-58
• 3.3.1 位置服务56-57
• 3.3.2 数据流检索57-58
• 3.4 LDCS算法58-63
• 3.4.1 搜索区域更新58-60
• 3.4.2 数据流的形成60-61
• 3.4.3 计算Skyline61-63
• 3.5 实验及性能分析63-67
• 3.5.1 仿真数据测试64-65
• 3.5.2 真实数据测试65-67
• 3.6 小结67-69
• 第四章 分布式环境中的Skyline计算69-87
• 4.1 引言69
• 4.2 背景知识69-74
• 4.2.1 P2P网络69-70
• 4.2.2 层次化P2P网络70-73
• 4.2.3 相关工作73-74
• 4.3 数据流环境下的连续Skyline计算74-85
• 4.3.1 问题定义74-75
• 4.3.2 基本思想75
• 4.3.3 树形路由结构的建立75-76
• 4.3.4 群内Skyline计算76-79
• 4.3.5 上层网络的Skyline计算79-81
• 4.3.6 实验及分析81-85
• 4.4 小结85-87
• 第五章 静态数据集上的反Skyline计算87-103
• 5.1 引言87
• 5.2 背景知识87-89
• 5.2.1 反Skyline概念87-89
• 5.2.2 相关工作89
• 5.3 BBRS算法89-91
• 5.4 RSBP算法91-96
• 5.4.1 算法思想92-93
• 5.4.2 R-树的建立93
• 5.4.3 并行计算93-96
• 5.5 算法分析96-97
• 5.6 实验及分析97-100
• 5.7 小结100-103
• 第六章 总结与展望103-105
• 6.1 本文工作总结103-104
• 6.2 研究展望104-105
• 参考文献105-113
• 致谢113-115
• 作者简介115

【相似文献】

中国期刊全文数据库 前10条

1 李志宽;;基于Skyline的企业总图3维信息系统[J];测绘与空间地理信息;2009年02期

2 向剑平;郑皎凌;;Skyline计算在多维排序问题上的分析[J];太原师范学院学报(自然科学版);2009年02期

3 黎刚;徐洁;陈踊;;基于Skyline的太湖流域水环境三维GIS系统设计与实现研究[J];现代商贸工业;2009年23期

4 黄丙湖;韩李涛;陈龙;;基于Skyline视频监控系统研究[J];地理信息世界;2010年03期

5 袁昱纬;;基于Skyline的铁路车站三维信息平台实现研究[J];办公自动化;2010年24期

6 周美娟;俞强;杨诗华;黄丽;;基于Skyline的公安三维GIS展现应用系统[J];测绘科学;2011年03期

7 张露露;陈宜金;;基于Skyline的数字矿山三维综合监测系统的应用研究[J];测绘信息与工程;2011年05期

8 邓瑞鹏;王意洁;李小勇;王媛;;基于数据垂直划分的高效并行Skyline查询[J];计算机工程;2012年14期

9 雷浩川;;基于Skyline的三维场景发布技术分析[J];测绘通报;2012年S1期

10 班鹏新;王元珍;朱虹;张勇;;面向标记安全数据库的Skyline立方体算法[J];华中科技大学学报(自然科学版);2013年02期

中国重要会议论文全文数据库 前10条

1 施朗;;浅谈Skyline平台建立三维网络地理信息系统的优缺点[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

2 葛洪涛;;基于Skyline的三维地理信息系统研究与设计[A];第二届“测绘科学前沿技术论坛”论文精选[C];2010年

3 陈秉政;;基于Skyline的三维管线系统的实现[A];第十四届华东六省一市测绘学会学术交流会论文集[C];2012年

4 雷浩川;;基于Skyline的三维场景发布技术分析[A];第四届“测绘科学前沿技术论坛”论文精选[C];2012年

5 雷明;张巍;陈利娟;;基于Skyline的水资源三维地理信息系统的设计与实现[A];水与水技术（第3辑）[C];2013年

6 刘剑;张应裕;王东博;周正玉;余建平;;基于Skyline的数字三维国土资源辅助决策系统设计与研发[A];广东省测绘学会第九次会员代表大会暨学术交流会论文集[C];2010年

7 刘莉;蔡军卫;田中彬;马彦;;一种基于移动Agent的分布式Skyline查询算法[A];2007年全国开放式分布与并行计算机学术会议论文集(下册)[C];2007年

8 张光伟;羌鑫林;赵建崇;;SketchUp配合下的Skyline快速三维运用[A];江苏省测绘学会2007年学术年会论文集[C];2008年

9 张光伟;羌鑫林;赵建崇;;SketchUp配合下的Skyline快速三维运用[A];江苏省测绘学会2007'学术年会论文集[C];2008年

10 赵连钧;;基于Skyline的高速公路3D GIS系统开发[A];中国公路学会计算机应用分会2010年学术年会论文集[C];2010年

中国重要报纸全文数据库 前1条

1 慕清;电子地图热点词汇[N];计算机世界;2007年

中国博士学位论文全文数据库 前3条

1 黄伯虎;多环境下Skyline计算问题研究[D];西安电子科技大学;2015年

2 孙圣力;数据流上Skyline查询处理算法研究[D];复旦大学;2008年

3 周红福;基于索引的Skyline算法研究[D];复旦大学;2007年

中国硕士学位论文全文数据库 前10条

1 吴大猛;延迟容忍网络中的Skyline查询研究[D];宁波大学;2014年

2 高天宇;非Skyline的Web服务提升方法研究与实现[D];昆明理工大学;2015年

3 蔡文明;高效关键词Skyline查询算法研宄[D];浙江大学;2015年

4 代博;无线传感数据的Skyline查询算法研究[D];大连海事大学;2015年

5 王雪菲;基于维度偏好的Skyline查询结果精简算法[D];大连理工大学;2015年

6 赵越;不确定数据流的分布并行Skyline查询处理技术研究[D];国防科学技术大学;2013年

7 李佼;基于Skyline的三维GIS开发关键技术研究[D];华东师范大学;2009年

8 胡清兰;路网中基于位置的多源Skyline查询研究[D];华南理工大学;2012年

9 宋世凯;基于Skyline的城市三维地理信息系统的设计与研究[D];河北师范大学;2012年

10 黄子晴;Skyline查询处理在文献检索排序中的应用研究[D];西安电子科技大学;2012年

  本文关键词：多环境下Skyline计算问题研究，由笔耕文化传播整理发布。

本文编号：295009