【作者】 廖巍；

【导师】 景宁；

【作者基本信息】 国防科学技术大学 ， 信息与通信工程， 2007， 博士

【摘要】 位置服务是通过移动终端和无线网络的配合,确定出移动用户的实际地理位置,从而提供用户需要的与位置相关的信息服务。位置服务技术融合了卫星导航、移动通信、Internet和数据库等当今IT行业的各种技术,形成一个独具特色、前景无限的新兴产业。随着全球定位系统、无线通信网络等基础设施的飞速发展和普及,面向位置服务的移动数据库技术已远不能满足用户不断增长的应用需求,面临着许多新的挑战。移动环境下,支持位置服务的移动对象数据库负责管理移动对象如汽车、飞机、舰船等位置信息,并提供相关查询服务。目前移动对象数据库领域的研究处于初步阶段,在理论和实际应用上还不成熟,存在许多问题和技术需要解决。针对移动对象当前和未来位置的索引技术和移动环境下的查询处理技术得到了国内外研究者的广泛关注,是充满挑战性的研究方向。论文研究目的是针对目前移动对象数据库领域中的研究难点和热点,在全面总结和分析国内外数据库领域相关工作的基础上,面向遥感卫星监视系统应用需要,对移动对象数据库系统的关键技术:移动对象索引技术、连续k近邻查询处理技术和预测范围聚集查询处理技术进行研究,力图进行创新,并将相关研究成果应用于实际系统中。本文的主要工作和创新点包括下面几个方面:(1)针对目前广泛使用的TPR树移动对象当前和未来位置索引在频繁更新应用中更新性能低下的问题,借鉴了R树BU算法思想,提出一种支持频繁更新的移动对象混合索引结构HTPR-tree,并给出了扩展的自底向上更新算法和更新代价模型。(2)深入分析TPR树索引查询性能随着时间变化急遽下降的问题,提出了一种基于速度分布的移动对象混合索引HVTPR树索引。HVTPR树索引综合考虑移动对象在速度域和空间域中的分布进行构建,具有良好的预测查询性能。(3)针对连续k近邻查询,引入了一种新的时空距离度量最小最大距离函数作为TPR树索引搜索时节点剪枝上界。提出了一种采用最优优先搜索策略的基于扩展时空距离度量的连续k近邻查询(STM-CNN)算法。STM-CNN算法利用最小距离函数进行TPR树索引节点搜索时访问排序,并使用最小最大距离函数对TPR树索引进行剪枝界定提高连续k近邻查询的搜索性能。(4)研究基于TPR树索引的大量并发连续k近邻查询处理技术,提出了一种可伸缩的增量连续k近邻查询处理SI-CNN框架,通过引入搜索区域进行裁剪以减少查询更新的所需要的磁盘访问代价,并引入了增量结果表批量的更新查询结果集。基于SI-CNN框架提出了一种支持更新的SI-CNN查询处理算法,基于上次查询结果增量的更新查询且支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作。(5)研究面向移动对象的精确预测范围聚集查询处理技术,提出了一种高效预测范围聚集查询索引(aTPR-tree)方法。通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价。aTPR树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性。基于aTPR树索引,提出了一种增强预测范围聚集查询(EPRA)算法,采用更精确的剪枝搜索准则,大大减少了查询所需要访问的节点代价。基于上述研究成果,论文最后构建了遥感卫星目标监视查询处理引擎原型系统和城市应急联动位置服务实验系统,验证了移动对象索引、连续k近邻及预测范围聚集查询技术的有效性和实用性。更多还原

【Abstract】 Location-based services provide users with services related to their positions which can be obtained through mobile devices and wireless networks infrastructure.The location-based services combine techniques in IT areas such as satellite navigation,mobile communications,internet and databases,thus have been becoming a unique and promising domain.With the repaid development of global positioning system(GPS),wireless cellular network,the moving objects databases techniques towards location-based services cannot meet the needs of users and face many challenges.In dynamic environment,the moving objects databases manage the positions of moving objects such as vehicles,airplanes and fleets,and provide location-dependent queries. Currently the researches in moving objects databases are preliminary and far from maturation both in theory and practice.And there are many open problems to solve.The indexing methods for current and future positions of moving objects and query techniques in dynamic environment,which are challenging directions,have been focused on by many researchers.In order to study the difficult and hot issues in moving objects databases,this paper gives comprehensive discusses and analysis on former work in related areas.And towards the application needs of satellite reconnaissance,this paper studies the key techniques in moving objects databases including indexing methods on moving objects, techniques of continuous k nearest neighbors query and predicted range aggregate query, and apply our achievements to practical applications.The main work and innovations are detailed as follows:1.A hybrid indexing method,HTPR-tree,which is based on TPR-tree and supplemented by a hash index,is presented to improve the lower performance of TPR-tree with frequent updates.Motivate by the bottom-up strategy of R-tree,an extended bottom-up update algorithm is developed for HTPR-tree and its cost model is also given.2.Based on thorough analysis on the query performance degrade of TPR-tree,we present a hybrid velocity distribution based time-parameterized R-tree(HVTPR-tree),which takes into account the distribution of both velocity domain and space domain and thus have a good query performance.3.In order to process continuous k nearest neighbors query based on TPR-tree efficiently,we present a new spatio-temporal distance metrics minmaxdist(t) as a pruning upper bound.Also a query algorithm based on extended spatio-temporal metrics (STM-CNN),searching in best-first manner,is developed.STM-CNN algorithm visits TPR-tree nodes according to mindist(t) order,and pruning the nodes with minmaxdist(t) to improve the query performance.4.To evaluate large collection of concurrent continuous k nearest neighbors queries continuously,we propose a scalable processing of incremental continuous k-nearest neighbor(SI-CNN) framework by introducing searching region to filter the visiting TPR-tree nodes.SI-CNN framework exploits incremental results table to buffer candidate objects and flushes the objects into query results in bulk.We then present an incremental SI-CNN query update algorithm,which evaluates incrementally based on former query answers and supports insertion or deletion of both query collection and moving objects.5.To improve the query performance of accurate predictive range aggregate(PRA) queries,we present an efficient predicted aggregate time-parameterized R-tree(aTPR-tree), which is based on TPR-tree structure and added with aggregate information in intermediate nodes to reduce the disk accesses of PRA queries.The aTPR-tree is supplemented by a hash index on leaf nodes,and uses bottom-up delete algorithm,thus having a good update performance and concurrency.Also an Enhanced predictive range aggregate(EPRA) query algorithm which uses a more precise branch and bound searching strategy is developed for aTPR-tree,reducing the node accesses greatly.Based on the above achievements,we design a remote sensing satellite targets reconnaissance query engine prototype and a location-based services experimental system fbr city emergency linkage to validate the efficiency and practice of our presented techniques including moving objects indexing methods,continuous k nearest neighbor query and predicted range aggregate query.更多还原