论文部分内容阅读
随着移动定位设备(如GPS)的出现和传感器网络的快速发展,产生了大量的时空数据或移动物体位置数据,因此,“基于位置的服务”(LBS)吸引了众多的研究,LBS的核心技术就是提供大规模的持续区域查询。建立查询索引是一种通用的加速持续区域查询处理的方法,常用的两种索引结构分别为网格和四叉树。对大规模持续区域查询而言,在建立索引结构的过程中,如何优化分解或存储过程,使得索引结构更优,提高查询处理的性能成为本文的研究点。本文在主流的CES索引结构基础上,分别在下面两个方面提出新的优化算法,以此提高查询处理性能:1.由于查询窗口在四叉树分割情况下,分割结果对查询窗口的左下角坐标是十分敏感的,所以在不改变查询窗口的前提下,提出了一种新的搜索大规模持续区域查询最优四叉树分割位置的优化算法,以此来减少分割的四叉树分割结果块,提高查询处理属性。2.基于四叉树和网格索引结构的不足之处,提出一种混合索引结构GridQuadtree和动态K值优化理论。根据大规模持续区域查询的四叉树分解结果,动态决定索引结构K值,降低四叉树深度,提高查询处理性能,同时在存储消耗上,也比单一的四叉树索引结构更低。由于持续区域查询都是通过数据流系统中自定义操作单元来实现的,本文在最后详细介绍了分布式数据流平台的查询处理引擎的设计,并给出持续区域查询的实验步骤和结果。