论文部分内容阅读
随着无线通讯技术、全球定位系统和地理信息系统的快速发展,基于位置的服务在交通引导、车辆跟踪、儿童看护、位置查询、紧急呼叫等领域内展现了广阔的应用前景,人们对于基于位置的查询服务需求更大,随着生活节奏加快,对时间效率要求变高,时间依赖路网下的位置查询服务更具有实际意义。现有方法从优化算法角度提高时间依赖路网下位置查询服务质量,目前所知没有时间依赖路网下满足多类型兴趣点查询的索引方法。本文对多类型兴趣点分布的时间依赖路网提出一种基于兴趣点分布进行网格合并的空间索引结构(TDG);首先在保证路网完整性与连通性的条件下,使用网格划分路网空间,根据子网中分布的兴趣点类型自底向上构建索引结构,提出基于路径权值上下界对预计算的路径进行剪枝的索引构建优化策略,减少预计算路径的存储空间。并提出索引维护更新策略。基于TDG索引结构,实现k近邻查询,范围查询,最快路径查询三种时空查询算法,并对最快路径查询算法进行优化。使用真实地图数据仿真实验表明在多类型兴趣点分布稀疏时基于TDG的k近邻查询算法平均扩展的结点数量比启发式查询算法减少87.5%,平均查询响应时间比启发式查询算法减少33%至66%;基于TDG的范围查询算法平均扩展的结点数量比启发式查询算法减少33%,平均查询响应时间比启发式查询算法减少50%;基于TDG的最快路径查询算法平均扩展的结点数量与平均响应时间比启发式查询算法减少34%-60%,可以看出,基于TDG的时空查询算法在兴趣点分布稀疏时优势明显且可以高效支持多类型兴趣点查询。