论文部分内容阅读
近几年来,随着移动信息技术的迅猛发展与集成了定位芯片的移动终端的迅速普及,云端能够非常方便的获取个人的出行轨迹。许多基于地理位置信息的研究层出不穷,同时也催生了大量相关应用。这些与时空轨迹相关的新兴研究和应用给人们的日常生活带来便利的同时也对空间数据库中时空轨迹数据的有效管理带来了很大的挑战。与此同时,如何高效利用这些海量数据已经成为了时空数据的管理和利用领域的研究热点。k-BCT查询(k Best-Connected Trajectories query)是最近提出的一种多查询点k最近邻轨迹对象搜索问题。其在旅游路线推荐以及个人出行模式研究上具有较为广泛的应用,但是由于k-BCT只考虑欧氏距离不考虑时间因素,对实际应用指导有限,因此本文提出了一种改进的查询模型,同时提出相应的两种应答算法,并通过实验证明了这两种算法的有效性。本文主要通过以下两个方面展开:1)通过分析k-BCT查询,发现k-BCT查询仅仅只考虑了轨迹点之间的欧氏距离,而定位日志中的轨迹点都具有时间属性,处在不同的时间段的轨迹具有不同的现实意义,通过进一步分析,得到k-BCT查询对现实生活的指导是有限的。因此,本文对k-BCT查询进行改进,得到了基于轨迹点权重的轨迹查询—k-WCT(k Weighted Connected Trajectories),k-WCT查询模型同时考虑了时间因素和欧氏距离,并分析得到k-WCT查询具备更好的现实指导意义。然后,为了设计一个有效的算法来应答k-WCT查询,本文提出了基于加权Max Rtree索引的轨迹搜索算法Rtree-FA,最后通过实验对比分析证明了该算法比k-BCT查询应答算法BF-O具有更高的搜索质量。2)尽管Rtree-FA算法能够较好的解决了k-WCT查询问题,但是该算法因为自身结构特点,具有查询次数多、计算消耗大、I/O占用高等缺陷。为了弥补Rtree-FA算法在查询性能较低与I/O占用高等方面的不足,为k-WCT查询带来更大的性能提升,本文借鉴加权Voronoi图,并将其与网格结合得到复合索引,并提出了基于复合网格索引的轨迹搜索算法Grid-FA。Grid-FA具有检索范围小、定位迅速、查询次数少、I/O消耗低等特点。最后通过实验对比分析,证明了本文提出的基于复合网格索引的Grid-FA算法比基于加权Max Rtree索引的Rtree-FA算法以及k-BCT查询应答算法BF-O具有更高的查询效率和更低的I/O占用率。