结合Voronoi图索引的路径Skyline查询处理技术

摘要

随着道路网规模的不断扩大，交通状况越来越复杂，行车环境的约束以及用户个性化的需求发展，使得用户希望能更多地将自己的要求加入到路径规划中。在实际生活中，影响用户选择路径的因素有很多，例如行程时间、行程距离、道路拥挤状况、个人偏好和出行目的等，这些因素导致用户选择路径的准则呈现多样性，将其应用于道路网以及路径规划系统中，能为用户提供满足多样性则准的路径集，具有很大的实际意义。论文研究了结合Voronoi图索引的路径Skyline查询处理技术，它为用户提供个性化的路径推荐服务。论文主要工作和创新点如下：
　　（1）研究了道路网中Skyline查询处理技术、路径选择算法以及道路网中的路径Skyline查询处理术的研究现状。给出了Skyline查询的传统定义，总结了经典的Skyline查询算法，分析这些算法的优劣势。并对道路网中的Skyline查询处理技术的研究现状进行分析介绍。分析介绍几种路径选择算法。分析并总结道路网中的路径Skyline查询处理技术的研究现状，并分别介绍几种通用路径Skyline查询算法和特殊路径Skyline算法。
　　（2）提出并研究了结合加权Voronoi图索引的多偏好有序路径Skyline查询处理技术，提出了道路网中对于多偏好有序路径的高效路径Skyline查询的基本算法及其改进算法。考虑多种数据点类型和路段的多种属性，由不同类型的数据点有序地组成的路径的聚合属性值作用于结果集，选取出满足用户偏好的有序路径Skyline。算法动态有序地探索子路径，利用加权Voronoi图索引的权值叠加特性对有序路径上的每个属性进行下界估计，获得在某一属性上的最优路径，将这些最优路径的属性值作为判断子路径支配的下界，以裁剪掉不可能被扩展成Skyline路径的子路径，提高有效路径的检索效率。实验表明，论文提出的方法在处理上述查询时，效率较高。
　　（3）提出并研究了结合加权Voronoi图索引的物体范围内路径Skyline查询处理技术，提出一种高效算法，实现在对兴趣点的查询范围有要求的情况下，对道路网中的物体范围路径Skyline查询。用具有不同权重的数据点集表示范围物体。算法根据路段多重属性对范围内的兴趣点和范围物体构建道路网加权Voronoi图索引，获得满足用户要求的范围物体，以及从用户起点到这些范围物体的属性最优路径，作为Skyline路径，在之后的路径动态探索过程，筛选出不被其他路径支配的Skyline路径，返回给用户满足其条件的Skyline路径集。

目录

声明

缩略词

第一章 绪论

1.1研究背景

1.2本论文的选题意义

1.3主要研究工作

1.4 论文组织结构

第二章 国内外研究现状

2.1道路网Skyline查询概述

2.2路径规划查询概述

2.3道路网路径Skyline查询概述

2.4本章小结

第三章 结合加权Voronoi图索引的多偏好有序路径Skyline查询

3.1加权Voronoi图索引

3.2有序多偏好路径Skyline查询

3.3算法实现

3.4实验测评

3.5本章小结

第四章 结合加权Voronoi图索引的物体范围路径Skyline查询处理技术

4.1问题描述与定义

4.2范围物体的加权Voronoi图索引结构

4.3结合加权Voronoi图索引的物体范围路径Skyline查询处理算法

4.4实验测评

4.5本章小结

第五章 总结与展望

5.1 论文工作总结

5.2 研究工作展望

参考文献

致谢

在学期间的研究成果及发表的学术论文