基于时空数据流的连续查询处理

摘要

目前，基于位置的服务(LBS)业务处于高速发展的阶段。在位置感知环境中，移动设备会产生大量的时空数据，服务器面临有限的系统资源和较高的实时性要求。传统的基于磁盘的时空数据库系统已经无法很好的适应这一需求。因此，将数据流处理技术与时空查询处理技术相结合就成为一个新的研究方向。设计一种高效的算法处理大量的连续时空查询和高速到达的时空数据流就成为当前的研究热点。
　　在分析现有的数据流和时空查询处理技术的基础上，本文给出了公路网环境下基于时空数据流的连续查询算法CQST(Continuous Queries on Spatio-temporaldata stream)。着重研究在处理时空查询时，通过有效利用输入数据的时空特性来降低查询计算量：(1)在生成查询计划阶段，通过引入共享执行结构的概念，将不同的时空查询逻辑映射到同一空间窗口操作符上，以此支持查询之间的共享；(2)通过利用移动对象和查询之间的位置、速度关系计算出某一时刻它们各自的“期望更新时间”，并根据此值丢弃或更新此刻之后到达的元组，从而避免不必要的空间连接操作。
　　本文对开源数据流系统STREAM进行扩展，使其支持时空查询。设计并实现了支持CQST算法的空间窗口操作符。最后在测试与性能分析中证实了算法的可行性。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 研究现状

1.3 研究内容及目标

1.4 本文组织

第二章 连续时空查询处理分析

2.1 数据流与时空查询

2.1.1 数据流技术

2.1.2 时空查询分类

2.2 连续时空查询模型

2.2.1 LBS中的时空查询

2.2.2关键技术

2.2.3 现有算法分析

2.3 问题描述和解决方案

2.4 本章小结

第三章 CQST连续查询算法

3.1 应用场景与限制

3.2 查询级的优化

3.2.1 连续时空查询实例

3.2.2 扩展的空间查询谓词

3.2.3 基于共享执行结构的查询计划

3.3 空间连接的优化

3.3.1 移动对象与范围查询

3.3.2 对象的期望更新时间

3.3.3 基于expTim的连续查询

3.3.4 期望更新时间的有效性

3.4 本章小结

第四章 系统设计与实现

4.1 系统体系结构

4.2 各模块的扩展

4.2.1 词法分析器

4.2.2 语义分析器

4.2.3 逻辑计划生成器

4.2.4 计划管理器

4.3 空间窗口操作符的设计

4.3.1 操作符内部框架

4.3.2 信息抽取及合并

4.3.3 查询结果的分发

4.3.4 时空查询处理流程

4.4 本章小结

第五章 测试与性能分析

5.1 测试环境

5.1.1 系统运行环境

5.1.2 测试数据

5.2 性能分析

5.2.1 不同网格大小对算法性能的影响

5.2.2 不同移动对象和范围查询数量对算法性能的影响

5.5 本章小结

第六章 总结与展望

6.1 总结

6.2 展望

致谢

参考文献

作者在读期间的科研成果