TPR-树在基于位置服务系统中的应用研究

作     者：金泽锋 

作者单位：江苏大学 

学位级别：硕士

导师姓名：薛安荣

授予年度：2008年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：时空数据库索引 空间位置预测查询 R-树 TPR-树 基于位置服务 

摘      要：时空数据库技术是计算机科学的新兴领域。面对着海量的数据,如何在给定的空间及时间范围内实现对移动对象快速有效地查询,是实现定位服务、智能交通、数字化战争等诸多应用中迫切需要解决的问题。时空索引技术是解决上述问题的关键技术。 TPR-树是一种可以对移动对象当前位置及未来位置进行有效索引的时空索引技术。TPR-树用TPBR(Time-Parameterized Bounding Rectangle)来近似表示对象,其基本算法和R-树类似。TPR-树不但支持对移动对象将来位置的预测查询,而且数据存储量和数据更新频率都相对较低。但TPR-树并没有得到广泛的应用,主要是因为其存在以下不足:对移动对象预测查询的精确度不高:TPBR之间的重叠随着时间的推移而越发严重,从而影响TPR-树的查询性能:算法的时间花费较高,不利于系统作出快速的响应。 本文对TPR-树的性能优化进行了研究。首先介绍了时空索引技术研究方面的成果。接着,根据TPR-树的特性,设计一种可以实现实时查询以及预测查询的基于位置服务系统。然后分别从四个方面对TPR-树进行研究以及改进:(1)通过引入记录的生命期,过期记录(expired entries)不再被真正删除,只是简单记载过期的时刻,从而使TPR-树可以应答对移动对象历史信息的查询;(2)对TPR-树所索引的数据对象进行扩展,使得TPR-树可以管理更为一般的数据对象;(3)提出一种同时考虑移动对象的空间属性和速度属性的结点分裂算法,算法在投影定积分值最大的轴上进行分裂,并把某段时间内子结点周长的定积分作为代价函数,不但降低了算法的计算时间,而且使用此算法所建立的TPR-树的查询速度也得到了一定的提高;(4)一种可以限制TPBR之间无限重叠的基于距离的结构调整策略,该算法通过强制重插在某个方向上的移动距离超过阈值的移动对象所对应的记录,从而达到调整TPR-树整体结构的目的。 实验表明,与原TPR-树结点分裂算法相比,改进后的结点分裂算法的计算时间降低了5～8倍,查询速度至少提高了50%:而且,在此基础上应用基于距离的结构调整策略使查询速度进一步提高约10%。