无线数据广播环境下的空间查询处理

摘要

随着移动智能终端设备的普及、无线通信技术和全球定位技术的发展，空间查询处理技术在日常生活中扮演者越来越重要的角色，并受到了工业界和学术界的广泛关注。在今天，空间查询处理技术在大量的领域得到了广泛应用，如个人出行活动管理、智能城市交通管理、救急服务、定位商业广告投放、以及基于位置的社交网络等。
　　传统的空间查询处理技术中所应用的数据访问模式是基于点对点模式的，即，移动终端通过无线网络，将自己当前位置信息和查询请求提交给服务器，服务器进行查询处理之后，将查询结果返回给移动用户。无线数据广播是无线环境中，实现空间查询处理的另一种模式。在该模式中，服务器负责将空间数据广播给移动用户，移动用户进入广播信道进行数据读取和查询处理。相对于传统点对点模式，无线数据广播更适用于用户数量巨大的情形，具有可伸缩性强、无线网络负载轻、移动终端节能性高、用户隐私零透漏的优点。在当今移动终端不断普及的背景下，无线数据广播环境下的空间查询处理具有非常大的研究意义和现实意义。
　　本文主要研究了无线数据广播环境下的路网最短路径查询、路网常用邻近性查询（包括范围查询、k近邻查询、连续k近邻查询）、以及空间字词检索。首先，本文提出了一种基于Hilbert曲线的树分解方法，并应用到无线数据广播环境下的最短路径查询处理，提出了一种节能性强的最短路径算法;接着，本文提出了无线数据广播环境下的路网邻近性查询处理算法，该算法首先将路网划分为若干网格，并计算网格之间的距离上下界，然后将网格索引和上下界作为索引，连同路网信息一起广播给用户;接着，本文研究了无线数据广播环境下的带关键字的空间查询处理，提出了一种基于网格索引和倒排表的空中索引;最后，通过真实数据和模拟数据，进行大量实验，验证了本文提出的方法的节能型和有效性。

目录

声明

摘要

第1章 引言

1．1．研究背景

1．2．研究意义

1．3．研究内容

1．4．本文工作

1．5．文章结构

第2章 相关工作

2．1．空间索引技术

2．1．1．基于R树的空间索引

2．1．2．基于四叉树的空间索引

2．1．3．基于网格的空间索引

2．2．空间查询处理技术

2．2．1．最短路径查询

2．2．2．路网邻近性查询

2．2．3．空间关键字查询

2．3．无线数据广播环境下的空间查询处理技术

2．4．本章小结

第3章 背景知识

3．1．无线数据广播

3．1．1．广播模式

3．1．2．衡量指标

3．2．树分解

3．2．1．树分解的基本定义

3．2．2．树分解的基本性质

3．2．3．基于树分解的最短路径查询算法

3．3．Hilbert曲线

3．4．倒排表

3．5．本章小结

第4章 无线数据广播环境下的最短路径算法

4．1．问题定义

4．2．算法描述

4．2．1．基于Hilbert曲线的树分解方法

4．2．2．BagIndex-基于Hilbert树分解的空中索引

4．2．3．基于BagIndex的数据组织

4．2．4．客户端查询算法

4．3．实验评估

4．3．1．算法性能指标

4．3．2．实验结果与讨论

4．4．本章小结

第5章 无线数据广播环境下的路网邻近性查询

5．1．NPI：基于网格划分的空中索引

5．1．1．路网的网格划分

5．1．2．预计算信息

5．1．3．数据段

5．1．4．索引分布和数据组织

5．2．客户端查询算法

5．2．1．范围查询

5．2．2．kNN查询

5．2．3．CNN查询

5．3．实验评估

5．3．1．实验配置

5．3．2．实验结果

5．4．本章小结

第6章 无线数据广播环境下的空间关键字查询

6．1．问题定义

6．2．算法描述

6．2．1．IRGI索引

6．2．2．索引分布和数据组织

6．2．3．客户端查询算法

6．3．实验评估

6．3．1．实验环境

6．3．2．实验结果与讨论

6．4．本章小结

第7章 总结和展望

7．1．本文总结

7．2．将来工作

参考文献

致谢

攻读硕士学位期间的研究成果