道路网skyline查询处理技术研究

发布时间：2017-08-06 16:07

  本文关键词：道路网skyline查询处理技术研究

  更多相关文章： 道路网 skyline查询 位置范围 道路支配路段 K近邻 安全范围 连续查询 移动对象

【摘要】：信息技术的发展使得人们获取信息的能力逐步提升,信息量急剧增大,形式也逐渐多样化,对数据库的存储能力和处理技术的要求也不断提高。Skyline查询作为一种能够在多属性数据中进行多准则优化的数据库操作得到大家的广泛关注。它能够帮助用户从海量数据信息中获取感兴趣的内容,从而做出正确的决策,在基于位置服务(Location-based Services,LBS)以及股票推荐,环境监测等领域具有重要的应用价值。现有的用于LBS的skyline查询技术大多针对非受限的欧式空间环境,而实际LBS应用中,我们所关注的大部分对象都处在受限空间,尤其是道路网环境中。对于道路网特殊的拓扑结构,已有的算法未能准确考虑其网络结构对查询对象距离属性的影响,以及对象点的非空间属性支配关系与道路网支配关系之间的联系,造成实际应用中算法的效率和精度都比较低。本文根据对已有算法的不足的分析,针对道路网环境,以实际应用场景为基础,研究道路网上的高效skyline查询算法,主要研究内容如下:(1)考虑静态LBS查询中定位设备精度和用户隐私保护的问题,研究了基于位置范围的道路网skyline查询。首先提出了一种基本的查询算法,根据范围边界替换定理将基于位置范围的skyline查询转为基于位置点的查询来实现。另外,为提高查询结果的精度,引入了道路网Voronoi单元构建道路网支配路段模型,并基于该模型提出了一种道路网skyline索引结构以及相应的查询算法,有效地提高了查询效率和查询精度。(2)考虑查询点沿道路网移动中连续查找距离较近的skyline对象点的问题,研究了道路网连续K近邻skyline查询,并提出了基于K近邻skyline安全范围的连续查询算法。算法通过引入道路网skyline集合安全范围和K近邻稳定序列范围,对当前K近邻skyline结果集进行维护,当查询点到达某边界点即将离开当前安全范围时触发相应的结果集和安全范围的更新,能够高效地支持连续K近邻skyline查询,避免连续快照查询的重复计算开销。(3)考虑查询数据集为道路网上的移动对象,研究了针对道路网移动对象的连续skyline查询问题,提出了一种基于事件触发的连续查询算法。首先道路网移动对象的特点建立相关的数据模型。之后,算法根据移动对象之间的距离交叉追踪对象间的支配关系,从而寻找需要进行结果集更新的时间点,以支持移动对象的连续查询。另外,算法中还引入了无效事件剪枝策略,减小了存储开销又提高了查询效率。
【关键词】：道路网 skyline查询 位置范围 道路支配路段 K近邻 安全范围 连续查询 移动对象
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要4-5
• ABSTRACT5-12
• 注释表12-14
• 第一章 绪论14-20
• 1.1 道路网查询技术的应用和研究现状14-16
• 1.2 本文的选题依据和意义16-17
• 1.3 本文的主要工作17-18
• 1.4 本文的组织结构18-20
• 第二章Skyline查询处理技术相关工作20-31
• 2.1 Skyline查询的基本概述20-21
• 2.2 静态skyline查询的经典算法21-25
• 2.2.1 不基于索引的算法21-23
• 2.2.2 基于索引的算法23-25
• 2.3 特殊环境下的skyline查询处理技术25-30
• 2.3.1 无线传感器网络上的skyline查询25-26
• 2.3.2 数据流上的skyline查询26-27
• 2.3.3 空间skyline查询27-29
• 2.3.4 道路网上的skyline查询29-30
• 2.4 本章小结30-31
• 第三章 基于位置范围的道路网静态skyline查询31-48
• 3.1 问题描述31-33
• 3.2 对象支配关系分析33-34
• 3.3 基本RNS查询算法34-36
• 3.4 道路网支配路段模型36-40
• 3.4.1 道路网Voronoi单元36-38
• 3.4.2 道路网支配路段38-40
• 3.5 基于索引的RNS查询算法40-43
• 3.5.1 SSR-tree索引结构40-42
• 3.5.2 基于SSR-tree索引的RNS查询算法42-43
• 3.6 实验与性能评估43-47
• 3.6.1 道路网规模对查询性能的影响44
• 3.6.2 POI中对象数量对查询性能的影响44-45
• 3.6.3 对象非空间属性维数对查询性能的影响45-46
• 3.6.4 查询范围大小对查询性能的影响46
• 3.6.5 查询精度的比较46-47
• 3.7 本章小结47-48
• 第四章 道路网连续K近邻skyline查询48-63
• 4.1 问题描述48-50
• 4.2 安全范围50-56
• 4.2.1 Skyline集合的安全范围50-53
• 4.2.2 K近邻稳定序列范围53-55
• 4.2.3 K近邻skyline复合安全范围55-56
• 4.3 动态维护56-58
• 4.3.1 Skyline集合的更新维护56-57
• 4.3.2 稳定序列维护57-58
• 4.4 基于安全范围的连续K近邻skyline查询算法58-59
• 4.5 实验与性能评估59-62
• 4.5.1 道路网规模对查询性能的影响60
• 4.5.2 POI中对象数量对查询性能的影响60-61
• 4.5.3 对象非空间属性维数对查询性能的影响61-62
• 4.5.4 参数k值对查询性能的影响62
• 4.6 本章小结62-63
• 第五章 道路网移动对象连续skyline查询63-75
• 5.1 问题描述63-65
• 5.2 道路网移动对象相关模型65-67
• 5.2.1 数据模型65-66
• 5.2.2 道路网移动对象的距离计算模型66-67
• 5.3 基于事件的移动对象连续skyline查询算法67-72
• 5.3.1 移动对象skyline的变化分析67-69
• 5.3.2 基于事件的E-MSKY查询算法69-72
• 5.4 实验与性能评估72-74
• 5.4.1 移动对象数据集大小对查询性能的影响72-73
• 5.4.2 移动对象非空间属性维数对查询性能的影响73
• 5.4.3 查询时间长度对查询性能的影响73-74
• 5.5 本章小结74-75
• 第六章 结束语75-77
• 6.1 本文的主要工作和贡献75-76
• 6.2 本文的不足和未来的研究方向76-77
• 参考文献77-82
• 致谢82-83
• 在学期间的研究成果及发表的学术论文83

【相似文献】

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

1 黄添强;卓飞豹;;移动对象查询研究进展[J];系统仿真技术;2007年04期

2 李伯权;;基于轨迹不确定的移动对象的预测处理[J];齐齐哈尔大学学报;2008年06期

3 王元芝;鄢来斌;;一种移动对象位置信息的处理方法[J];计算机工程与科学;2009年12期

4 李实吉;秦小麟;施竣严;;障碍空间中的移动对象位置预测[J];计算机科学;2014年07期

5 易善桢,张勇,周立柱;一种平面移动对象的时空数据模型[J];软件学报;2002年08期

6 吴劲;卢显良;;移动对象数据模型[J];计算机科学;2002年06期

7 董毅,Edward Chan,黄载禄;LDCQ的距离更新策略[J];华中科技大学学报(自然科学版);2003年12期

8 李国徽;钟细亚;;一种基于固定网络的移动对象运动轨迹索引模型[J];计算机研究与发展;2006年05期

9 卢炎生;查志勇;潘鹏;;一种改进的移动对象时空数据模型[J];华中科技大学学报(自然科学版);2006年08期

10 廖巍;唐桂芬;景宁;钟志农;;基于速度分布的移动对象混合索引方法[J];计算机学报;2007年04期

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

1 翁敬农;;移动对象及其时空模型的研究[A];中国地理信息系统协会第九届年会论文集[C];2005年

2 张伟;皮德常;;挖掘移动对象的频繁运动模式[A];2009年中国智能自动化会议论文集（第三分册）[C];2009年

3 曹会萍;丁治明;王珊;孟小峰;;移动对象管理的自适应索引方法[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

4 胡志智;孟小峰;郭研妍;李本钊;陈继东;;基于模拟预测的移动对象位置主动更新策略[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

5 陈滨;丁治明;纪鹏程;;基于动态交通网络的移动对象的索引[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

6 王波涛;陈贺;马俊;喜连川优;王国仁;;基于区域覆盖的移动对象索引的设计与实现[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

7 涂丹丹;向琳;左德承;杨孝宗;;移动对象数据库管理技术[A];黑龙江省计算机学会2007年学术交流年会论文集[C];2007年

8 白芸;孟小峰;丁锐;杨楠;胡志智;;基于移动对象流的道路索引[A];第二十届全国数据库学术会议论文集（研究报告篇）[C];2003年

9 刘小峰;陈传波;刘云生;;移动对象全局K最接近邻居查询研究[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

10 赵亮;陈荦;景宁;钟志农;;一种高效的移动对象连续多范围查询处理框架[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

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

1 中国人民大学信息学院 孟小峰 丁治明;让数据跟随你移动[N];计算机世界;2001年

2 中国人民大学信息学院 郝兴;移动数据管理待补课[N];中国计算机报;2008年

3 ;Word中的“微调”技术[N];中国计算机报;2005年

4 四川 余文勇;课件特殊效果巧实现[N];中国电脑教育报;2001年

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

1 吴佩莉;移动对象轨迹数据管理关键技术研究[D];北京理工大学;2015年

2 杨彬;室内移动对象的数据管理[D];复旦大学;2010年

3 叶李;移动对象数据库查询及处理技术研究[D];电子科技大学;2011年

4 张恒飞;空间数据库中移动对象位置管理技术研究[D];华中科技大学;2012年

5 方颖;移动对象数据库中移动对象索引方法研究[D];武汉大学;2010年

6 廖巍;面向位置服务的移动对象索引与查询处理技术研究[D];国防科学技术大学;2007年

7 陈楠;时空数据库中移动对象的索引和查询技术研究[D];浙江大学;2010年

8 赵亮;面向位置服务的移动对象并发查询处理技术[D];国防科学技术大学;2010年

9 张凤荔;移动对象数据智能处理模型研究[D];电子科技大学;2007年

10 袁冠;移动对象轨迹数据挖掘方法研究[D];中国矿业大学;2012年

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

1 黄川林;室内移动对象轨迹分析研究[D];中国科学技术大学;2014年

2 王梦冉;蜂窝网中基于频繁轨迹的越区切换算法研究[D];西南交通大学;2015年

3 金琨;不确定环境下移动对象轨迹模式挖掘及路径规划研究[D];西南交通大学;2015年

4 易显天;面向位置服务的道路网络下的汽车索引技术研究[D];电子科技大学;2015年

5 毕彦博;优化的基于Voronoi图的移动对象K近邻查询算法的研究与实现[D];东北大学;2013年

6 孙清清;面向移动对象间状态查询优化算法的研究与实现[D];东北大学;2013年

7 杨雨;面向GPS的移动对象轨迹模式挖掘研究[D];东北大学;2014年

8 张盼盼;融合复合特征的移动轨迹预测方法的研究与实现[D];西安电子科技大学;2014年

9 吴昊;基于路网的移动对象位置管理关键技术研究[D];南京邮电大学;2015年

10 李岳昌;基于代价聚簇的城市路网移动对象索引技术[D];南京邮电大学;2015年

，

本文编号：630496