一种面向集合的空间关键词查询方法研究

摘要

如今，定位技术的快速发展使得基于位置的服务得到了广大移动用户的青睐。随之而来的，各种拥有定位技术的移动设备不断推陈出新，各种基于位置信息和文本信息的查询被提出。为了满足这样的查询需求，学术界对于不同条件的查询需求分别提出了各种高效的空间关键词查询算法。空间关键词查询按类别分为，单一对象匹配的空间关键词查询，面向集合的空间关键词查询，面向集合和方向的空间关键词查询。不同类型的查询，在不同的查询条件或不同的查询环境中，也有各种不同的查询算法。
　　道路网是人们生活空间的抽象，研究道路网上的空间关键词查询更有实际意义和使用价值。到目前为止，人们还没有研究过道路网上方向和集合同时被考虑的空间关键词查询。在前人的研究基础上，本文提出了一种基于道路网的面向集合和方向的空间关键词查询方法。首先，把整个道路网分割成几个相连的局域网，以局域网层次的结构建立空间索引，为每个局域网建立倒排索引，目的是每次查询时，可以快速的跳过不包含查询关键词的区域直接进入下一个包含查询关键词的局域网进行查询。然后，找到在指定查询方向上并且在指定查询范围内的局域网。最后，在获得可查询的局域网内，查询出满足查询文本信息和空间位置信息及查询范围约束的一条路线，这条路线满足:1）路线上的空间对象文本信息能够共同满足查询的文本信息;2）此路线是最优的路线，即查询用户从查询位置出发，走此路线能把所要做的事情完成，并且是代价（可以是行走的路程或者行走的时间或者所消耗的费用等）最小。
　　本文针对道路网上面向集合且受查询方向约束的空间关键词查询，提出了面向无主关键词的查询和主关键词优先的查询。无主关键词的查询即从查询点出发按照道路网在可查询范围内扩展查询。主关键词优先的查询，首先在可查询范围内以一种迭代替换的方式进行扩展查询直到查询到主关键词对象，若还有关键词没有被已查询到的空间对象所覆盖，则以面向无主关键词的查询方式继续进行扩展查询。本文对这两种查询分别给出了查询算法。最后，分别对以上两种查询进行了实验，证明了所提算法的有效性。

目录

声明

摘要

第1章 绪论

1．1 课题的研究背景及意义

1．1．1 课题的背景

1．1．2 课题的意义

1．2 国内外研究现状

1．2．1 基于欧式距离的空间关键词查询研究现状

1．2．2 基于路网距离的空间关键词查询研究现状

1．3 主要研究内容和预期研究成果

1．4 本文的组织结构

第2章 课题的相关研究

2．1 R树、R*树和倒排列表

2．1．1 R树和R*树

2．1．2 倒排列表

2．2 欧式空间中的复合索引模型

2．2．1 KR*树

2．2．2 BR*树

2．2．3 IR2树

2．2．4 IR树

2．3 路网上的索引技术

2．3．1 基础知识

2．3．2 局域网

2．3．3 对象摘要和短割

2．4 本章小结

第3章 空间索引的构建

3．1 研究概述

3．2 道路网的划分

3．2．1 局域网层次

3．2．2 对象摘要和短割的创建

3．3 索引树的构建

3．3．1 局域网IR树索引

3．3．2 局域网层次索引

3．4 本章小结

第4章 查询算法的实现

4．1 问题的相关定义

4．2 面向无主关键词的查询算法

4．2．1 算法思想

4．2．2 算法描述

4．3 面向主关键词优先的查询算法

4．3．1 算法思想

4．3．2 算法描述

4．4 本章小结

第5章 实验及结果分析

5．1 实验数据集及实验平台

5．2 实验结果及分析

5．3 本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢