大数据环境下道路网Top-k查询优化技术研究与实现

摘要

最近十年以来，移动互联网得到了快速的发展并产生了巨大的变革，也引发了各种移动设备的快速普及。同时移动设备上的各种应用也在不断的丰富和改变着我们的生活。在各类应用中，基于位置的服务（Location-Based Service）就是其中很重要的一类。而LBS中一个经典的查询模式就是Top-K查询，即根据用户所在的位置，查询出某类POI点中最近的K个结果，例如：查找出计算机学院周围最近的K个银行。目前Top-K查询方面已有不少研究工作，但是普遍存在两点不足：1、查询大多基于直线距离，无法基于道路网距离排序；2、无法支持海量数据级别的查询。
　　为了解决道路网Top-K查询问题，本文首先分析了现有算法优缺点。其次结合实际应用，提出了一个基于平衡K叉树的道路网索引结构DS-Tree。DS-Tree通过对道路网的划分以及预处理等工作，能提高Top-K查询时的效率。本文证明了该索引的正确性，并分析了建立索引的空间和时间效率。与此同时，为了适应大数据环境下的道路网查询需求，本文研究了MapReduce环境下DS-Tree索引的建立与更新方法。最后结合实验对比，验证了算法的正确性和效率。

目录

封面

中文摘要

英文摘要

目录

第 1章 绪 论

1.1 研究背景

1.2 国内外研究现状

1.3 相关技术背景

1.4 本文结构安排

第 2章 道路网 Top-K查询问题定义与分析

2.1 道路网 Top-K查询问题定义

2.2 道路网 Top-K查询问题难点分析

2.3 相关研究成果分析

2.4 本章小结

第 3章 DS-Tree索引的设计

3.1 相关准备工作

3.2 图的动态收缩树 DS-Tree

3.3 DS-Tree的空间复杂度分析

3.4 本章小结

第 4章 DS-Tree上的查询过程与分析

4.1 DS-Tree正确性的证明

4.2 DS-Tree上的 Top-K查询算法

4.3 DS-Tree上的查询过程

4.4 查询算法的几个实现细节

4.5 Border 点上的索引

4.6 DS-Tree上索引正确性的证明

4.7 本章小结

第 5章 MapReduce 下 DS-Tree索引的建立过程

5.1 道路网的层次划分

5.2 MapReduce 下子图内多源最短路径的计算

5.3 MapReduce 下子图收缩的计算

5.4 建立 Border 点上的倒排索引

5.5 DS-Tree索引更新机制

5.6 本章小结

第 6章 实验与结果分析

6.1 实验环境

6.2 实验数据准备

6.3 道路网划分效率分析

6.4 建立索引效率分析

6.5 查询效率实验

6.6 本章小结

结论

参考文献

声明

致谢