详情

原文传递时间依赖路网查询处理技术研究

论文题名：	时间依赖路网查询处理技术研究
关键词：	时间依赖路网;移动对象;KNN查询;Skyline查询;位置服务
摘要：	基于位置的服务已成为个人应用中的基础服务。其中路网查询技术又是极为重要的技术，目前针对路网查询问题进行的工作主要分为基于欧式距离查询和基于路网距离查询两种。现用户在考虑传统静态路网采用的通行距离成本之外，还十分重视时间成本，即相应道路的通行时间。因此将其纳入道路查询研究范围有着十分重要的现实意义，同时也有非常广阔的应用前景。　　与传统研究的静态路网不同，时间依赖路网中道路的权重是随时间的推移而改变，这一特性使得基于此类路网的查询更加接近日常出行情况，但现有算法在查询效率上有所不足且主要针对最短路径及近邻问题。本文在对现有路网查询技术充分分析的基础上，结合实际路网应用场景，站在查询用户的角度，以时间依赖路网为基础从KNN查询、Skyline查询和KNN-Skyline查询三种技术种类对时间依赖路网查询技术展开研究，主要工作概括如下：　　(1)针对现有的方法解决时间依赖路网上移动对象KNN查询服务效率低下的问题，提出了一种在反向时间依赖路网上基于最短路径树的移动对象KNN查询算法TDSPT-KNN。该方法基于由兴趣点出发到达查询用户用时最短的需求，建立反向时间依赖路网进行初始化；然后启发式选取标记点并建立相应最短路径树，从而动态维护时间依赖路网上的最短路径，并在最短路径树的基础上采用三角形不等式对距离计算进行剪枝，而后构造启发式函数引导搜索进一步优化查询，高效扩展。在德国奥尔登堡路网数据集上，比NN-Reverse-TD算法在查询效率提升了六成。　　(2)针对现有方法未能有效解决时间依赖路网上移动对象连续Skyline查询的问题，提出了一种求解时间依赖路网上移动对象连续Skyline查询的算法TDSP-MS。算法基于时间依赖路网上移动对象的动态特性构建出对应的数据模型，找出查询对象与查询点间动态路网关系，从而减小距离计算开销。在此基础上，沿用最短路径树存储，同时针对移动对象模型及TDRN-Skyline问题特性进一步剪枝优化查询，根据分析得到的移动对象间的路网支配关系找到连续查询结果集的更新时间戳，同时引入多种无效条件对其进行进一步剪枝优化。在德国柏林和奥尔登堡城市路网数据集上进行实验，实验结果表明TDSP-MS算法在处理时间依赖路网上移动对象的连续Skyline查询上具有高效性。　　(3)针对时间依赖路网上查询较近Skyline对象点的需求及引入偏序域属性后结果集不可控的问题，提出了一种基于KNN的时间依赖路网Skyline查询算法TDMI-KS。算法在考虑用户实际需求后加入静态固定点的相应偏序域属性，通过与用户进行多次交互，构建出对象点属性支配矩阵，对时间依赖路网对象点进行偏好属性快速索引并关联更新结果集，极大约减非空间支配关系，结合最短路径树对路径动态维护后，基于时间依赖路网上的KNN查询方法对结果集进行剪枝优化更新。在德国奥尔登堡路网数据集上进行四个维度实验分析，在不同参数下，实验结果表明TDMI-KS算法的有效性和高效性。
作者：	宋力翔
专业：	计算机科学与技术
导师：	秦小麟
授予学位：	硕士
授予学位单位：	南京航空航天大学
学位年度：	2021