论文部分内容阅读
基于位置服务(Location Based Services, LBS)应用随着地理信息系统(Geographic Information System,GIS)和移动定位、3G技术的发展而迅猛增长,手持设备端要处理的空间数据也越来越大。本文在移动云计算环境下开发LBS应用大规模拼车系统。开发移动云计算中的应用,高效地处理日益增长的海量数据是至关重要的需求以及挑战。传统的空间数据索引具有局限性,只有高扩展性、分布式的空间索引才能更高效地完成大规模空间数据查询分析的任务。目前有利用MapReduce模型对空间查询索引进行并行化实现的方法,如基于R-tree以及Voronoi图的索引并行化。这些方法存在着不足：R-tree不适合于进行并行化：基于Voronoi]图的索引,可以用于并行化,然而进行查询时需要对局部索引进行重建计算。相比于以上两种方法,网格索引更易于扩展和并行化。而倒排索引利用有限的索引条目就可以为无限的数据点建立索引。结合网格索引和倒排索引的优点,本文提出倒排网格索引,利用MapReduce编程模型,将倒排网格索引建立过程并行化。倒排网格索引更简单、无共享而且松耦合,因此适合用于MapReduce并行化建立。基于倒排网格索引,本文提出KNN算法的并行化,KNN查询算法利用多线程方式进行并行化,可以加速k近邻的查找效率。并行化倒排网格索引和KNN查询技术,在处理大规模位置数据方面具有高效性。最后,本文在倒排网格索引结构和并行KNN算法基础上,开发了大规模拼车系统,一方面验证了倒排网格索引和并行KNN算法处理大规模空间数据的性能,一方面满足了人们出行便捷打车的需求。本文所提出的云计算空间索引以及查询技术适用于开发基于位置服务的应用,同时为LBS应用开发提供了新思路。