原文传递
道路网skyline查询处理技术研究
| 论文题名： | 道路网skyline查询处理技术研究 |
| 关键词： | 道路网;skyline查询;移动对象;位置服务;索引结构 |
| 摘要： | 信息技术的发展使得人们获取信息的能力逐步提升，信息量急剧增大，形式也逐渐多样化，对数据库的存储能力和处理技术的要求也不断提高。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查询问题，提出了一种基于事件触发的连续查询算法。首先道路网移动对象的特点建立相关的数据模型。之后，算法根据移动对象之间的距离交叉追踪对象间的支配关系，从而寻找需要进行结果集更新的时间点，以支持移动对象的连续查询。另外，算法中还引入了无效事件剪枝策略，减小了存储开销又提高了查询效率。 |
| 作者： | 施常月 |
| 专业： | 计算机科学与技术 |
| 导师： | 秦小麟 |
| 授予学位： | 硕士 |
| 授予学位单位： | 南京航空航天大学 |
| 学位年度： | 2015 |
| 正文语种： | 中文 |
检索历史
应用推荐
