本文選題：LBS + 倒排網(wǎng)格索引��； 參考：《大連海事大學(xué)》2013年碩士論文

【摘要】：基于位置服務(wù)(Location Based Services, LBS)應(yīng)用隨著地理信息系統(tǒng)(Geographic Information System,GIS)和移動定位、3G技術(shù)的發(fā)展而迅猛增長,手持設(shè)備端要處理的空間數(shù)據(jù)也越來越大。本文在移動云計算環(huán)境下開發(fā)LBS應(yīng)用大規(guī)模拼車系統(tǒng)。開發(fā)移動云計算中的應(yīng)用,高效地處理日益增長的海量數(shù)據(jù)是至關(guān)重要的需求以及挑戰(zhàn)。傳統(tǒng)的空間數(shù)據(jù)索引具有局限性,只有高擴展性、分布式的空間索引才能更高效地完成大規(guī)�？臻g數(shù)據(jù)查詢分析的任務(wù)。目前有利用MapReduce模型對空間查詢索引進(jìn)行并行化實現(xiàn)的方法,如基于R-tree以及Voronoi圖的索引并行化。這些方法存在著不足：R-tree不適合于進(jìn)行并行化：基于Voronoi]圖的索引,可以用于并行化,然而進(jìn)行查詢時需要對局部索引進(jìn)行重建計算。 相比于以上兩種方法,網(wǎng)格索引更易于擴展和并行化。而倒排索引利用有限的索引條目就可以為無限的數(shù)據(jù)點建立索引。結(jié)合網(wǎng)格索引和倒排索引的優(yōu)點,本文提出倒排網(wǎng)格索引,利用MapReduce編程模型,將倒排網(wǎng)格索引建立過程并行化。倒排網(wǎng)格索引更簡單、無共享而且松耦合,因此適合用于MapReduce并行化建立�；诘古啪W(wǎng)格索引,本文提出KNN算法的并行化,KNN查詢算法利用多線程方式進(jìn)行并行化,可以加速k近鄰的查找效率。并行化倒排網(wǎng)格索引和KNN查詢技術(shù),在處理大規(guī)模位置數(shù)據(jù)方面具有高效性。最后,本文在倒排網(wǎng)格索引結(jié)構(gòu)和并行KNN算法基礎(chǔ)上,開發(fā)了大規(guī)模拼車系統(tǒng),一方面驗證了倒排網(wǎng)格索引和并行KNN算法處理大規(guī)�？臻g數(shù)據(jù)的性能,一方面滿足了人們出行便捷打車的需求。本文所提出的云計算空間索引以及查詢技術(shù)適用于開發(fā)基于位置服務(wù)的應(yīng)用,同時為LBS應(yīng)用開發(fā)提供了新思路。
[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.
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2013
【分類號】：P208;TP3

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 趙華;王海闊;;移動云計算綜述[J];電腦知識與技術(shù);2012年01期

2 李建江;崔健;王聃;嚴(yán)林;黃義雙;;MapReduce并行編程模型研究綜述[J];電子學(xué)報;2011年11期

3 黃敬良;郝忠孝;;移動對象的K個連續(xù)最近鄰查詢算法[J];哈爾濱理工大學(xué)學(xué)報;2007年06期

4 宋曉宇;孫業(yè)挺;孫煥良;;支持動態(tài)負(fù)載的移動對象最近鄰查詢算法[J];計算機工程與應(yīng)用;2007年27期

5 朱承璋;張舸;楊紅;;淺析移動云計算技術(shù)研究現(xiàn)狀[J];科技信息;2011年34期

6 閆成印;;2011年移動互聯(lián)網(wǎng)回顧與未來展望[J];互聯(lián)網(wǎng)天地;2012年02期

7 王淼;;基于Voronoi圖的最近鄰查詢的索引結(jié)構(gòu)的研究[J];齊齊哈爾大學(xué)學(xué)報;2006年06期

8 羅軍舟;金嘉暉;宋愛波;東方;;云計算:體系架構(gòu)與關(guān)鍵技術(shù)[J];通信學(xué)報;2011年07期

9 鄭榕增;林世平;;基于Lucene的中文倒排索引技術(shù)的研究[J];計算機技術(shù)與發(fā)展;2010年03期

10 陳如明;;大數(shù)據(jù)時代的挑戰(zhàn)、價值與應(yīng)對策略[J];移動通信;2012年17期

，

本文編號：2075729