道路网中分布式关键词查询算法研究

摘要

道路网是现实生活中地图的抽象，其结构为一个带边权重的图。其中，图顶点代表在道路网中的一个路段交界位置或是一个重要地理位置（如景区，重要医院，著名大学等），而两点之间的连边代表一个路段。连边的权值代表该路段的长度（或者需要行驶的时间）。有了这样的道路网数据库，可以提供基于位置的服务(Location-based Service)。代表性的应用像Google Local和YahooMaps已经得到越来越广泛的应用。一种更为广义的道路网图结构则是每个图顶点都附有相应的描述信息，如“复旦大学正校门”可以描述复旦大学正校门地理位置对应的顶点。有了带文本的道路网数据库，我们可以进行基于关键词的位置信息查询，如“找到距离复旦大学正校门500米以内的邮局”。这类基于关键词的道路网查询丰富了基于位置的服务。我们将这类空间关键词查询严格定义为关键词组合查询。
　　本文首先研究了道路网中关键词组合查询如何利用分布式环境加速查询。我们提出分布式索引技术来加快查询计算，并从理论上证明了索引空间的最优意义。其次，我们指出，提出的分布式索引技术适用于一个更广义的查询类，我们称其为Q类，并证明提出的方法对于整个Q类查询的可行性。Q类查询能够处理诸如“找到距离超市和医院都比较近的位置”，“找到距离当前位置500米以内的所有中餐馆”等查询。我们考虑了两种实验设置:Hadoop MapReduce集群以及一个基于协调器的集群，并分别提出了分布式算法。在基于协调器的分布式环境中，我们通过实验比较了NPD索引算法相比于集中式算法的效率和可扩展性优势。在Hadoop集群环境中，我们针对Hadoop环境的特性提出了朴素的查询算法，基于简单索引的查询算法和基于NPD索引的查询算法，并通过详尽的实验比较说明基于索引的查询算法的效率优势和强可扩展性。

目录

摘要

第一章 引言

1．1 研究背景和意义

1．2 研究内容和研究成果

1．3 本文结构

第二章 相关工作

2．1 道路网中的最短路查询

2．2 欧式空间关键词查询

2．3 基于关系数据库或其图结构的关键词查询

2．4 基于XML的关键词查询

2．5 道路网上关键词查询

2．6 本章小结

第三章 NPD索引及其查询算法

3．1 概念与问题定义

3．2 一种集中式算法

3．3 分布式算法概述

3．4 NPD索引结构

3．4．1 SC结构

3．4．2 DL结构

3．4．3 NPD索引的正确性和最优意义

3．4．4 进一步剪枝

3．5 索引生成和查询

3．5．1 按块并行索引生成

3．5．2 分布式空间关键词组合查询

3．6 分析和扩展

3．6．1 复杂性和负载均衡

3．6．2 多条最短路的情况

3．6．3 从关键词组合查询到Q类查询

3．7 实验结果

3．8 本章小结

第四章 MapReduce下的路网索引与关键词查询词处理

4．1 MapReduce计算模型

4．2 MapReduce下的朴素算法

4．2．1 朴素算法的缺点

4．2．2 MapReduce下的简单索引SI(Simple Index)

4．2．3 MapReduce下的NPD索引

4．3 实验结果

4．4 本章小结

第五章 总结与展望

致谢

学术论文

参考文献

声明