移动云计算下位置服务数据管理与应用研究

发布时间：2018-06-27 23:40

本文选题：LBS + 倒排网格索引　；参考：《大连海事大学》2013年硕士论文

【摘要】：基于位置服务(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应用开发提供了新思路。
[Abstract]:With the development of Geographic Information system (GIS) and mobile positioning technology (3G), the application of location based Services (LBS) is growing rapidly. This paper develops a large scale carpool system for LBS applications in mobile cloud computing environment. The development of mobile cloud computing applications and efficient processing of the growing mass of data is a critical requirement and challenge. The traditional spatial data index has its limitations. Only with high scalability and distributed spatial index can the task of query and analysis of large-scale spatial data be completed more efficiently. At present, there are methods to implement spatial query index parallelization using MapReduce model, such as index parallelization based on R-tree and Voronoi diagram. These methods are not suitable for parallelization: indexes based on Voronoi diagrams can be used for parallelization, but local indexes need to be reconstructed when querying. Compared with the above two methods, the grid index is easier to extend and parallelize. The inverted index uses a limited number of index entries to index an infinite number of data points. Combined with the advantages of grid index and inverted index, the inverted grid index is proposed in this paper. Using MapReduce programming model, the establishment process of inverted grid index is parallelized. The inverted grid index is simpler, non-shared and loosely coupled, so it is suitable for MapReduce parallelization. Based on inverted grid index, a parallel KNN query algorithm is proposed in this paper, which can speed up the search efficiency of k-nearest neighbor. Parallel inverted grid indexing and KNN query techniques are efficient in dealing with large scale location data. Finally, on the basis of inverted grid index structure and parallel KNN algorithm, a large-scale carpool system is developed. On the one hand, the performance of inverted grid index and parallel KNN algorithm in dealing with large-scale spatial data is verified. On the one hand, it meets the demand of convenient taxi. The spatial index and query techniques proposed in this paper are suitable for the development of location-based applications and provide a new idea for LBS application development.
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：P208;TP3

【参考文献】