论文部分内容阅读
随着移动通信、GPS空间定位、电子地图等技术的快速发展,基于位置的服务(Location-based Services,LBS)在交通导航、安全防卫、生活娱乐等领域受到了广泛关注。Skyline查询从具有多维属性的数据集合中返回具有优势的子集,近年来成为了数据库查询领域一项重要的研究课题。论文研究了道路网中基于位置的Skyline查询处理技术,它根据查询点的位置信息,为用户提供个性化的推荐服务。论文主要工作和创新点如下:(1)考虑道路网中移动查询点连续查找一定范围以内的Skyline数据点的问题,研究了道路网中连续范围Skyline查询处理技术,提出了基于动态断点设置策略的连续查询方法。对于每一条路段,该方法首先采用基于道路网Voronoi图改进的增量路网扩展方法,计算获得该路段对应的候选Skyline点集,然后使用动态断点设置策略,动态获得断点集合,当查询点移动到某一断点所在位置时,根据断点信息,更新Skyline查询结果集,从而实现连续查询。实验表明,论文提出的方法在处理上述查询问题时,效率较高。(2)考虑到城市道路网交通状况日益复杂,距离最近的目标兴趣点不一定可以在最快的时间内到达,论文提出并研究了双重属性道路网中k序列Skyline查询问题。在双重属性道路网中,每条边有两条属性,分别为该边的欧氏距离属性和通过该边所需要花费的时间属性。根据用户对路网中边的距离属性和时间属性的偏好,k序列Skyline查询问题被分为距离最优k序列Skyline查询和时间最优k序列Skyline查询。针对每种查询,提出两种方法来计算Skyline,第一种为基本的路网遍历扩展算法,第二种为基于距离(时间)约束的改进算法。实验表明,第二种算法减少了磁盘读取次数,降低了CPU运行时间,提高了Skyline查询算法的效率。(3)考虑到Skyline查询在国内外有着广泛的研究,但基本上都限于理论算法。论文在研究理论算法的同时,基于QT开发框架,将论文第三章、第四章介绍的道路网中连续范围Skyline查询和双重属性道路网中k序列Skyline查询嵌入到一个可视化原型系统里。该原型系统底层采用真实的加州道路网地图数据,选择相应的查询功能并设置参数,即可进行相关Skyline查询并返回相应的查询结果。系统交互性较好,对Skyline查询研究有指导促进作用。