云计算环境下的大规模空间近邻查询算法研究

摘要

随着移动互联网与物联网等技术的迅猛发展，出现了大量的带有位置信息的数据，这给大规模空间数据的索引与查询带来了一系列的需求与挑战。近邻查询作为典型的算法已广泛应用于数据挖掘、支持决策系统，商业定址等领域。现有的索引技术与近邻查询算法，因为内在的顺序性执行与基于内存设计的算法所限，而无法直接应用于大规模空间数据处理中。本文深入研究如何在分布式环境下进行可扩展的空间索引与查询算法设计。
　　首先，本文提出了新的分布式空间数据索引方法:倒排空间网格索引。该索引是将分布式倒排索引与空间网格划分方法相结合。松耦合与无共享的结构使得倒排网格索引具备良好的可扩展性。
　　其次，在云计算环境中基于我们的索引结构，设计了云计算环境下的并行轮圈遍历与分布式kNN查询算法。证明了kNN查询算法的收敛性，并将计算性能与可扩展性与同类算法在分布式环境下进行了实验比较。
　　最后，实现了基于倒排空间网格索引的Basic-SRNN基准算法和Lazy-SRNN、Eager-SRNN两个优化算法来有效地处理大规模的多维RNN查询。其中Lazy进行延迟剪枝所有的空间数据点，Eager-SRNN采用流的方式进行查询空间的增量剪枝。并证明了kNN查询算法的精确性与完备性。大量的真实与仿真的数据集上完成的实验分析结果表明，我们实现的大规模反近邻查询在不同实验条件下均优于当前最好的算法。

目录

声明

摘要

第1章 绪论

1．1 研究意义与背景

1．2 国内外研究现状

1．2．1 空间数据的分布式计算技术

1．2．2 大规模空间数据索引研究

1．2．3 分布式近邻查询研究

1．3 论文主要工作与创新点

1．4 研究内容与论文结构

第2章 大数据处理方法与技术

2．1 云计算与大规模数据管理

2．1．1 大数据的背景与定义

2．1．2 云计算

2．1．3 移动云计算

2．2 大数据处理系统与机制

2．2．1 大数据服务模型

2．2．2 分布式文件系统

2．2．3 数据虚拟化与存储平台

2．2．4 大数据处理系统

2．3 MapReduce与优化技术

2．3．1 MapReduce技术介绍与问题分析

2．3．2 MapReduce索引与优化

2．3．3 MapReduce查询与优化

2．4 大数据在云应用中的挑战

2．5 本章小结

第3章 基于网格的大规模空间数据索引研究

3．1 大规模空间数据索引技术

3．1．1 空间数据的特征

3．1．2 传统空间数据索引方法

3．1．3 大规模空间数据索引的问题

3．2 分布式空间索引方法与分析

3．2．1 R树索引与分布式处理

3．2．2 泰林索引与分布式处理

3．2．3 网格索引与分布式处理

3．3 基于网格的倒排索引

3．3．1 倒排索引技术

3．3．2 倒排空间网格索引

3．3．3 基于MapReduce的倒排网格索引实现

3．3．4 倒排网格索引进一步优化

3．4 实验结果与分析

3．4．1 实验环境与数据集

3．4．2 实验结果与分析

3．5 本章小结

第4章 空间分布式最近邻查询

4．1 最近邻查询算法

4．2 分布式kNN查询算法

4．2．1 分布式kNN查询算法

4．2．2 ParallelCircleTrip算法

4．2．3 ParallelCircleTrip算法的收敛性证明

4．3 实验结果与分析

4．3．1 数据集大小的影响

4．3．2 k大小的影响

4．3．3 当计算节点变化时的影响

4．4 本章小结

第5章 大规模多维反近邻查询

5．1 反最近邻查询算法

5．2 Basic-SRNN基准算法

5．3 Lazy-SRNN优化算法

5．4 Eager-SRNN优化算法

5．5 SRNN算法证明与效率分析

5．5．1 算法精确性与完备性证明

5．5．2 SRNN算法分析与比较

5．6 实验结果与分析

5．6．1 网格宽度的影响

5．6．2 非分布式环境性能

5．6．3 可扩展性对比测试

5．6．4 SRNN算法间比较

5．7 本章小结

第6章 空间大数据检索平台设计与算法应用

6．1 空间大数据检索系统架构设计

6．1．1 研究现状分析

6．1．2 空间大数据检索平台架构

6．1．3 大规模空间查询系统与数据结构

6．2 其它大规模空间查询算法应用

6．2．1 双色反近邻查询

6．2．2 高维LSH索引与查询

6．3 本章小结

第7章 总结与展望

7．1 本文的主要工作与结论

7．2 对未来工作的研究与展望

参考文献

攻读学位期间公开发表论文

攻读学位期间主持和参与的主要科研项目

致谢

作者简介